如何實現動態大小的哈希表？

我知道散列表數據結構的基本原理。如果我有一個大小爲N的哈希表，我必須儘可能均勻地將數據分配到這N個存儲桶中。如何實現動態大小的哈希表？

但在現實中，大多數語言有其內置的哈希表類型。當我使用它們時，我不需要事先知道散列表的大小。我只是把我想要的東西放進去。例如，在Ruby：

h = {} 
10000000.times{ |i| h[i]=rand(10000) }

它怎麼能這樣做？

來源

2012-03-25 Lai Yu-Hsuan

見the Dynamic resizing section of the Hash table article on Wikipedia。

通常的做法是使用與a dynamic array相同的邏輯：擁有一定數量的存儲桶，並且當散列表中有太多項目時，創建一個具有較大大小的新哈希表並將所有項目移動到新的哈希表。

另外，根據哈希表的類型，這種調整大小可能不是必要的正確性（即它仍然會工作，即使不調整），但它肯定是必要的性能。

來源

2012-03-25 13:52:14 svick

一個很好的換湯不換藥的方法是將表的規模擴大一倍，然後當你搜索一個值，則其哈希鍵，並在哈希表做modulu搜索以'哈希％current_size'，然後'哈希％current_size/2'等等。當你找到這個值時，你可以重新哈希它。這樣你就可以做懶惰的重整，而不會失去太多的性能，因爲通常訪問的值會自動重新加入。 – 2012-03-25 13:59:52

@DvirVolk，懶惰rehash很好。您已經知道最頂級哈希表中的條目，並知道從哪個哈希表中刪除。但是，當某些條目可以容納整個空桶時，您可能會遇到這種情況。這種「增量大小調整」，從維基是數據，因爲我明白大小tradoff速度的解決方案（最後你持有2個* N個區段，其中N是最上面的哈希表的大小）。雙倍尺寸是很好的的事實，你必須單桶與重用舊桶的鏈表分成兩個或合併兩個成一個（沒有哈希重新計算）「複製所有條目」。 – ony 2012-03-25 14:17:22

如何實現動態大小的哈希表？

回答

相關問題