分析哈希函数中素数的用法

Question

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

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;
}

我想理解为什么在下面这个解释的背景下使用偶数乘以每个字符是一个坏主意（在另一个论坛上找到;它听起来像一个很好的解释，但我没有抓住它）。如果以下推理无效，我将不胜感激。

假设MULT为26，并考虑散列一百个字符的字符串。字符串的第一个字符对'h'的最终值有多大影响？第一个字符的值将被MULT乘以99次，因此如果算术以无限精度完成，则该值将包含一些混乱的位，后跟99个低位零位 - 每次乘以MULT，您将引入另一个低阶零，对吧？计算机的有限算术只是砍掉了所有多余的高阶位，所以第一个字符对'h'的实际贡献是......精确为零！ 'h'值仅取决于最右边的32个字符串字符（假设为32位int），即使这样，事情也不是很好：最后32个字节中的第一个仅影响最左边的“h”位并且没有效果剩下的31个。显然，一个有价值的MULT是一个糟糕的主意。

Answer 1

会产生一个独特的价值

停在那儿。哈希不是唯一的。一个好的哈希算法可以最大限度地减少冲突，但是鸽子原理确保我们无法完全避免冲突（对于任何具有非平凡信息内容的数据类型）。