重整後的預期鏈長 - 線性散列

Question

我對加載因子有一個困惑。一些消息來源表示，它只是散列表中的密鑰數量除以總插槽數量，這與每個插槽的預期鏈路長度相同。但那只是簡單的統一哈希權？

假設哈希表T有n個元素，我們通過使用h'（k）= k mod 2m對它們進行重新哈希來重新分配時隙T [0]中的元素，從而將T擴展爲T1。如果h（k）> 1，那麼T1的哈希函數爲h（k）= k mod 2m。如果h（k）爲012並且k mod m如果h（k）≥1。許多消息來源表示，「擴展並重新哈希以保持負載因子這意味着期望鏈長度仍然是相同的？）由於這不是簡單的均勻散列，我認爲任何密鑰k進入一個時隙的概率是（1/4 + 1/2（m-1）） 對於密鑰k （隨機選擇），首先評估h（k）（小於1或大於或等於1的機會是50-50），如果小於1，則密鑰k只有兩種方式 - 插槽0或時隙m，因此，概率1/4（1/2 * 1/2）但是如果它大於或等於1，它具有m-1個時隙並且可以輸入任何概率（因此概率爲1/2 * 1/m-1），所以預期的鏈長度現在是n/4 + n/2（m-1），我在正確的軌道上嗎？

Answer 1

線性散列的計算應該與「非線性」哈希。使用特定的初始桶數，均勻分佈的散列值將導致統一的佈局。如果有足夠的擴展來擴大表的大小，那麼每個值將通過增量重新散列在較大的空間中隨機分配，新值也將分佈在較大的空間中。每增加一點，當表格擴大到該長度時，每個點同樣可能位於（初始桶位置）和（2x初始桶位置）。

有一篇文章here詳細介紹了在不同情況下（不僅僅是平均值）的鏈長計算，特別是線性哈希。