哈希中間方法

我正在閱讀有關中心哈希方法的中間方法。哈希中間方法

這裏筆者提到，其中有大量的前導零的鑰匙將發生碰撞。

類似的推理適用於具有大量尾隨零的鍵。

請求給出一個例子和解釋作者在上述兩個語句中的含義。

如方法所述，鑰匙x除以2^(w-k)。在位級這實際上意味着x的位被右移(w-k)。

現在採取一種情況，其中x = 7,(w-k) = 3。所以x = 00000111和意味着x = 00000000將這些位向右移。

現在，你會注意到，對於x從7 (00000111) to 0 (00000000)的所有值，位移將導致00000000（將位右移總是將0附加到左側）。因此具有大量前導0（7到0）的值將碰撞到相同的散列。

2014-09-23 10:07:29 Haris

感謝您的澄清。我對上面的解釋x有2 ^（w-k）的分歧，我認爲我們是右移不左移。問題在於作者如何精確確定中間數字，是如何將x * x >>（w-k）給予中間數字 – venkysmarty 2014-09-23 10:34:46

我的錯誤，這些數字正在向右移動。最終會在左邊追加0。 @venkysmarty – Haris 2014-09-23 10:36:16

見。採取不同的例子。 'x = 8（00000100）'不用2 ^（w-k）除以2將得到散列值'00000001'。從'x = 8'我們得到'0001'，這是'x'的中間位。 @venkysmarty – Haris 2014-09-23 10:40:22

回答