如何選擇散列表的大小？

Question

假設我有200,000個單詞，並且我將使用hash*33 + word[i]作爲散列函數，對於最小內存/分頁問題，​​應優化哪個表的大小？

平臺使用 - C（C99版），

詞是英文字符的話，ASCII值哈希表的

一次初始化

用於搜索（鏈接列表樣式桶），接下來就像字典搜索一樣。

碰撞後，該詞將作爲新節點添加到桶中。

Answer 1

一個好的經驗法則是保持負載因子在75％或更少（有些人會說70％）以保持（非常接近）O（1）查找。 假設你有一個很好的散列函數。

基於此，您至少需要大約266,700個桶（對於75％）或285,700個桶（對於70％）。這是假設沒有碰撞。

也就是說，你最好的選擇是用不同散列表大小的樣本數據進行一次測試，看看你得到多少次碰撞。

您可能還會考慮比hash*33 + word[i]更好的散列函數。 Jenkins hash及其變體需要更多計算，但它們提供了更好的分佈，因此通常會減少衝突並減小所需的表格大小。

你也可以在這個問題上拋出內存。 500,000的表格大小爲您提供40％的最小負載因數，這可以彌補散列函數的缺點。但是，你很快就會達到收益遞減點。也就是說，使表格大小爲1百萬，給你一個20％的理論載入率，但幾乎可以肯定的是，你實際上並沒有意識到這一點。

長話短說：使用更好的散列函數並在不同的表大小下進行一些測試。

有這樣的事情作爲minimal perfect hash。如果你知道你的輸入數據是什麼（即它不改變），那麼你可以創建一個保證O（1）查找的散列函數。這也非常節省空間。但是，我不知道爲200,000個項目創建一個最小完美散列會有多困難。