關於哈希表的幾個問題

Question

我一直在閱讀很多關於哈希表的知識，以及如何在C語言中實現，我想我幾乎擁有了所有的概念，所以我可以開始編寫自己的代碼，我只是有幾個問題我還沒有正確理解。

作爲參考，我一直在閱讀這樣的： http://eternallyconfuzzled.com/jsw_home.aspx

1）正如我已閱讀上述網站，二的冪或素數對被推薦用於散列表的大小。這基本上是一個數組，並且數組的大小是固定的，所以我可以快速查找我正在查找的值。我不能聲明一個小數組，如果我有一個很大的輸入，因爲它不適合，我不能聲明一個非常大的數組，如果我的輸入數據不是那麼大，因爲它浪費了內存。

什麼是散列表的最佳大小？我應該根據什麼決定？

2）此外，在該網站上，有一些哈希函數，我還沒有閱讀它們。它還指出，最好使用一個衆所周知的算法並推出我自己的算法。我可以做到這一點，我會從該網站挑選一個並在我的代碼上進行測試，並根據我的輸入數據查看是否最小化了衝突。

什麼在擾亂我是如何控制散列範圍？哈希無法返回，並且整數大於哈希表大小，否則我們會遇到嚴重問題。我如何處理這個問題？

Answer 1

1）您所指的是散列表的加載因子 - 預計要填充的存儲桶的百分比。維基百科有這樣一段話：

有了好的哈希函數，平均 查找成本是從0 客座率上升至0.7 左右幾乎恆定。除此之外，處理它們的衝突概率和代價爲 增加。

我相信Java的實現（可能還有其他）會定期調整大小以保持負載因子在可接受的範圍內。

2）只需使用模運算符（％）來保持存儲區索引合法。第二個操作符應該是您的存儲區陣列的大小。

Answer 2

爲你的散列表選擇一個小尺寸。當你添加東西到你的表中時，檢查一下表中正在使用的表的百分比。當它大於70％滿時，使桌子變大。例如，刪除元素時也是如此 - 例如，當表格小於60％時，表格變小。維基百科對動態調整大小的一些策略有很好的描述，但這是一般的想法。

如果你知道你將在哈希表中存儲的數據量的大小的粗略順序，這是通常不夠好，只是創建：

，因爲你似乎已經知道輸入的數據我只說一張關於那個大的表格。 （你不應該擔心是否一切都會合適，相反，正確的想法是你會碰到多少碰撞，以及你將如何處理它們。）

至於正確的散列函數，有可能你的輸入結構將建議哪一個將是正確的。例如，您的輸入的哪些方面可能會均勻分佈？