調整哈希表的大小有意義嗎？什麼時候？

Question

我的哈希表實現有一個函數，當負載達到約70％時調整表的大小。我的哈希表是用單獨的鏈進行碰​​撞實現的。

是否有意義，我應該在任何時候調整哈希表的大小，還是應該讓它保持原樣？否則，如果我在負載爲70％時增加尺寸（差不多是兩倍，實際上我遵循這個：http://planetmath.org/encyclopedia/GoodHashTablePrimes.html），當負載變爲30％或更低時，是否應該調整它的大小？

Answer 1

你是在編寫一般用途的散列表，還是有特定的目的呢？我建議不要爲了一般實現而調整較小的尺寸。這將使你的表格變得簡單並且在經常填充和清空表格的情況下防止內存抖動。如果最終遇到散列表需要縮小的情況，請在該時間點擴展它。

Answer 2

如果內存很便宜，請保持獨立。如果內存昂貴，請按照您的建議重新調整歇斯底里。完成後，分析結果以確保其表現良好並且沒有做出愚蠢的事情。

Answer 3

如果您有一個高質量的散列函數（見here），則散列表不必具有素數長度。你可以使它們成爲兩個冪，這大大加快了索引計算的速度。

爲什麼這與這個問題有關？因爲當你縮小兩次冪的哈希表時，你可以將所有的條目保留在下半部分的位置，並簡單地將鏈接列表添加到槽i（從上半部分）到槽i - n/2的鏈接列表中。