Hashing谷歌面试

Question

为什么不能通过权力的2或权力的10或素数是好的散列函数？如果我们想要在一个散列函数中存储溢出记录，为什么这些散列函数选择不好？

Answer 1

假设你的散列函数返回一个32位无符号结果。假设你选择了一个4096的模数。你所做的实际上是：index = hash & 0xFFF - 所以，你丢掉了哈希值的前20位。现在，如果你的散列值是真的好，最低的12位和其余的一样好，那么这不是问题。然而，如果你的哈希值在所有32位上都很好，但是最低的12位值是可疑的（例如，它们可能受到字符串最后一个字符的影响更大）......那么你可能会后悔舍弃前20位在这种情况下，如果选择任何奇数模数，则index = hash % modulus的结果取决于散列的所有32位。

所以，更一般地，如果你的散列计算模M，你的指数被视为hash % N，那么你要的是你的M和N进行互质。

M如果是2^m（因为它通常是这样），那么N=10^n是不好的选择，因为所得index底部n位是散列的底部n比特的直副本。