哈希中间方法

Question

我正在阅读有关中心哈希方法的中间方法。

http://www.brpreiss.com/books/opus4/html/page212.html

这里笔者提到，其中有大量的前导零的钥匙将发生碰撞。

类似的推理适用于具有大量尾随零的键。

请求给出一个例子和解释作者在上述两个语句中的含义。

Answer 1

如方法所述，钥匙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）的值将碰撞到相同的散列。