c++ - 散列函数中质数的使用分析

Question

我正在研究基于散列的排序，我发现在散列函数中使用素数被认为是一个好主意，因为将键的每个字符乘以一个素数并将结果相加会产生一个唯一值(因为素数是唯一的)并且像 31 这样的素数会产生更好的 key 分布。

key(s)=s[0]*31(len–1)+s[1]*31(len–2)+ ... +s[len–1]

示例代码:

public int hashCode( ) 
{
    int h = hash;
    if (h == 0) 
    {
        for (int i = 0; i < chars.length; i++) 
        {
            h = MULT*h + chars[i];
        }
        hash = h;
    }
    return h;
}

我想明白为什么在下面这个解释的上下文中使用偶数来乘以每个字符是一个坏主意(在另一个论坛上找到；这听起来是个很好的解释，但我没能理解).如果以下推理无效，我将不胜感激更简单的解释。

Suppose MULT were 26, and consider hashing a hundred-character string. How much influence does the string's first character have on the final value of 'h'? The first character's value will have been multiplied by MULT 99 times, so if the arithmetic were done in infinite precision the value would consist of some jumble of bits followed by 99 low-order zero bits -- each time you multiply by MULT you introduce another low-order zero, right? The computer's finite arithmetic just chops away all the excess high-order bits, so the first character's actual contribution to 'h' is ... precisely zero! The 'h' value depends only on the rightmost 32 string characters (assuming a 32-bit int), and even then things are not wonderful: the first of those final 32 bytes influences only the leftmost bit of `h' and has no effect on the remaining 31. Clearly, an even-valued MULT is a poor idea.

Answer 1

我认为使用 2 而不是 26 更容易看出。它们对 h 的最低位具有相同的效果。考虑一些字符 c 后跟 32 个零字节(用于说明目的)的 33 个字符串。由于字符串不完全为空，因此您希望散列值不为零。

对于第一个字符，您计算的哈希 h 等于 c[0]。对于第二个字符，您采用 h * 2 + c[1]。所以现在 h 是 2*c[0]。对于第三个字符 h 现在是 h*2 + c[2]，计算结果为 4*c[0]。再重复 30 次，您会发现乘法器使用的位多于目标中可用的位，这意味着 c[0] 实际上对最终哈希完全没有影响。

使用不同的乘数(如 26)，最终的数学计算结果完全相同，只是中间哈希值会在过程中每隔一段时间对 2^32 取模。由于 26 是偶数，它仍然在每次迭代的低端添加一个 0 位。