哈希函數和表格的大小表格2^p

Question

在從密鑰的哈希碼計算哈希表桶索引時，爲什麼我們在分區（模）時避免使用餘數是2的力量？

Answer 1

在計算散列時，您需要儘可能多的信息，因爲您可以在整個位的範圍內以低成本實現事物分配，例如： 32位無符號整數通常很好，除非你有大量（> 30億）的項目存儲在散列表中。

它將哈希碼轉換爲您真正感興趣的桶索引。當桶的數量n是2的乘方時，您需要做的就是在哈希碼h和（n -1），結果等於h mod n。

這可能不好的一個原因是AND操作只是簡單地丟棄哈希碼中的比特 - 高位比特。這可能是好的或壞的，取決於其他事情。一方面，它會非常快，因爲AND比分割快很多（並且是你選擇使用2個桶數的權力的常見原因），但是另一方面，可能存在較差的哈希函數較低位的熵較差：也就是說，當散列數據改變時，較低位不會有太大變化。

Answer 2

讓我們說，表大小是m = 2^p。 讓k是一個關鍵。然後，每當我們做k mod m時，我們只會得到k的二進制表示的最後p個比特。因此，如果我放入幾個具有相同最後p位的密鑰，散列函數將非常糟糕地執行，因爲所有密鑰都將散列到表中的同一個插槽。因此，避免冪2