動態哈希表使用鏈散列

Question

我試圖實現使用鏈散列動態哈希表的執行情況（陣列中的每個元素是一個鏈表）。 我想知道，複雜明智的，它的下面可能是更好的： 1.當數組已滿，這意味着每個鏈表至少有一個元素，我應該加倍數組大小。 2.當我總共有N個元素時（在所有鏈表中），我應該將數組大小加倍 - 其中N是數組大小。

Answer 1

大量的散列表實現在野外，包括C++標準中的幾個（unordered_set，unordered_map）。

要回答你的問題，最好是折起來的箱數（內部數組），當元素計數到達N的其他方式將更難和耗時（找出如果所有垃圾桶都滿）。

你需要保持持有的元素數量的成員。

您不必擔心使用像{ return 0;}這樣的不良散列函數的用戶。

Answer 2

複雜性的角度來看，他們都是一樣的。散列表的複雜性以平均大小寫的O（1）給出，因爲一旦散列函數具有良好的散列函數，散列衝突就可以歸結爲運氣。無論你做什麼，任何散列表的最壞情況複雜度都是O（N）。

也就是說，有用的實現基於負載因子調整大小，該負載因子是總元素和桶數（「數組大小」）之間的比率。等到每個存儲桶至少有一個條目時，往往會導致次優行爲。但是載荷因子1（N個桶中的N個元素）可能過高;大多數實現我已經看到默認0.7左右（10個桶7個元素），並且通常讓用戶配置負載因子（請參閱C++和Java兩者）。這是交易內存與速度，哈希表通常都是關於速度。一般來說，只有分析才能顯示任何特定程序的正確值。

此外，大小不需要一倍。典型的vector實現每個調整大小的大小增加50％或70％，因爲對實際應用程序的大規模測試表明，更好的速度/內存摺衷比雙倍。它有理由相似的事情將適用於散列表，雖然這再次受到分析。