c# - 哈希码非零初始值 - 注意 : I am not asking about primes

Question

这是一种学术观点，但如果我不理解为什么像 Effective Java 和许多 SO 问题这样的书籍推荐它，我觉得我没有完全理解哈希码。

假设:

public sealed class Point
{
    private readonly int x;
    private readonly int y;

    //constructor ommited

    //equals ommited
    
    public override int GetHashcode()
    {
       int hash = 17; //why should the initial value be non-zero?
       unchecked
       {
         hash = hash * 31 + x; //do not tell me why I should use primes - that is not the question
         hash = hash * 31 + y;
         return hash;
       }
    }
}

现在，据推测，初始值的原因是它减少了其中一个组件为零的碰撞。

我正在努力寻找任何这有帮助的例子。

这是一个碰撞示例，但具有初始值不会产生任何几率。

x   y   Hash Without initial value     Hash With initial value  
0   31  31                             16368                
1   0   31                             16368                

理想情况下，我正在寻找一个初始值可以防止碰撞的具体示例。

我关于为什么初始值永远不会产生影响的理论

//Given a prime p, initial value i, fields a,b,c, calculate hash h
h = i;
h = h*p + a;
h = h*p + b;
h = h*p + c;

因此:

h = ((i*p + a)*p + b)*p + c
  = (ipp + ap + b   )*p + c
  = ippp + app + bp + c

因此初始值 i 将通过生成一个常量值以相同的方式影响所有哈希码，在本例中为 i*p³.

Answer 1

初始值必须是素数。为什么？因为假设您正在散列以获取长度 = 20 的数组的索引:[object.getHash()%20] 是您要存储对象的数组的索引。 如果您使用了偶数:数据结构的一半地址将永远不会被使用...这就是您需要使用初始值的原因:最小化冲突...并最大化数据结构的使用