需要幫助開始構建我自己的散列表

我正在學習散列表，試圖瞭解它們是如何工作的。我想製作一個相當簡單的哈希表，使用單獨的鏈接（使用數組中的列表）。我有幾個問題：需要幫助開始構建我自己的散列表

假設鍵可以是任何類型的，我會要求用戶執行散列函數，對不對？這可以避免嗎？
用戶還需要提供包含在初始化的列表（碰撞）所述陣列的長度，正確？這可以避免嗎？

如果你有任何其他的提示，或者一些散列表的C++的清晰的代碼示例，我會感激。

感謝您的幫助。

2012-02-07 xcrypt

通常情況下，是的，你就需要在客戶端指定的散列函數，因爲如果你正在寫一個通用的哈希表和任意類型T的操作，你可以不知道如何哈希它的方式，在語義上是有意義的。您可以通過在存儲的元素類型和散列函數上對類進行參數化來完成此操作。例如：

template <typename T, typename Hash = std::hash<T>> 
    class MyHashTable { 
    /* ... */ 
}

在這裏，您可以使用默認參數和模板來選擇默認散列函數，除非用戶另有指定。

雖然客戶端通常可以指定表的初始大小，它不是必需的。您可以對桶的數量進行有根據的猜測（比如，最初使用17個桶），隨着負載因子的增加，增加表的數量。這是類似的，比如說，如何std::vector工作：實現可以選擇默認的大小，但如果客戶端，也確實需要一個預先篩分的載體或來電reserve，實施從用戶需要的提示。例如，你可以有形式

template <typename T, typename Hash = std::hash<T>> 
    class MyHashTable { 
public: 
    MyHashTable(unsigned numBuckets = 17); 
}

這樣的構造，客戶可以只構建一個哈希表桶的默認號碼，或者如果他們有桶的數量感，他們會就像他們可以將其指定爲參數一樣。但是，您可能還想隱藏存儲桶作爲細節，只需讓客戶端指定要將多少元素放入表中，然後讓您的類在幕後執行計算。這使得後臺切換實現變得更加容易，因此，如果您想使用動態完美哈希表而不是鏈式哈希，類可以處理計算初始大小的複雜性。

至於代碼示例，我不知道如何提供任何不放棄很多參與建設哈希表的複雜性。 :-)如果您有一段特定的代碼感興趣，並且無法自行編寫代碼，請隨時將其作爲單獨問題發佈，以便獲得更有針對性的反饋。

希望這會有所幫助！

來源

2012-02-07 22:23:23 templatetypedef

看的哈希算法的各種實現方式。有很多可用的。如果你願意，你可以讓哈希存儲變量。隨你便。使用大多數哈希算法，碰撞是可能的。記住這一點。

來源

2012-02-07 22:23:35

我不知道這是如何解決這個問題。如果你正在構建你自己的散列表，那麼你可能希望客戶端提供散列算法，因爲你可能事先不知道存儲的類型是什麼。此外，由於這是C++，因此您可以使用'std :: hash'來執行散列。 – templatetypedef 2012-02-07 22:28:29

如果你想了解哈希表，我建議你開始用最簡單的人至極的線性鏈哈希表

在這裏，您考慮的指針（指針的固定大小的數組類型的定義項目你）你的物品將被存儲在哪裏，考慮還有一些計數器，一個用於跟蹤陣列的長度，另一個用於跟蹤添加到表中的物品的數量，直到某個時刻

你可以使用宏定義將項添加到哈希表的功能，如下所示

h(k) = k % M

其中k是要添加的項目的索引（鍵），M是表示指針數組大小的質數（例如13,29,41,543）和h（k）會給你該項目將被插入的位置。

你應該考慮使用指針的固定大小的數組的原因是因爲這種方式，您有

O(n)

成本。

因此，從這個簡單的功能，那麼你可以修改它，並考慮實施一些更復雜的像開放adressing，線性探測，二次探測和雙散列

對於用戶要求對項目的數量輸入i開始完全同意什麼templatetypedef說早些時候

來源

2012-02-07 22:47:13

需要幫助開始構建我自己的散列表

回答

相關問題