为什么 2 的幂或 10 的幂或素数不能成为好的散列函数？如果我们想在散列函数中存储溢出记录，为什么那些不适合散列函数的选择呢？
问问题
518 次
1 回答
4
假设您的散列函数返回一个 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是一个糟糕的选择，因为n结果的底部位是哈希index底部位的直接副本。n
于 2014-09-21T11:45:14.693 回答