散列码非零初始值 - 注意:我不是在问素数

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

初始值的选择永远不会对哈希产生影响。

\n

例子：

\n

//Given a prime p, initial value i, fields a,b,c, calculate hash h\nh = i;\nh = h*p + a;\nh = h*p + b;\nh = h*p + c;\nh = h % 2^32;\n

\n

所以：

\n

h = (((ip  + a) * p + b) * p + c) % 2^32\n  = (( ip\xc2\xb2 + ap     + b) * p + c) % 2^32\n  = (  ip\xc2\xb3 + ap\xc2\xb2    + bp     + c) % 2^32\n  = ip\xc2\xb3 % 2^32 + (ap\xc2\xb2 + bp + c) % 2^32\n

\n

因此，初始值i将以相同的方式影响所有哈希码，即在本例中为哈希添加一个常量值i*p\xc2\xb3 % 2^32。

\n