6

这是一种学术观点，但如果我不明白为什么如 Effective Java 和许多 SO questions 等书籍推荐这样做，我觉得我不完全理解哈希码。

认为：

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*p3。

4

4 回答 4

2

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

于 2012-11-19T15:31:00.427 回答
1

通过实验和测试表明，使用素数对散列函数具有良好的特性。
您在现有库中看到的硬编码数字，例如31在测试期间Java发现它们是不错的选择。据我所知，这些“神奇”数字的选择背后没有任何证据。它们是在现场测试后才选择的

更新：
如果您使用零作为初始值，那么您的哈希将受到成员变量的影响，也为零。
例如hash = hash * 31 + x;，0如果x是0，你的初始值也是0。
然后你最终得到y哪个也可能是0或者一个在你的应用程序域中可能很常见并最终导致冲突的数字

于 2012-11-19T15:45:06.447 回答
0

初始值可用于区分不同类的对象。

您上面显示的哈希函数不是很好，很容易导致具有不同属性值的对象发生冲突。散列函数的想法是，它根据公共属性产生唯一或几乎唯一的值。

因此，要获得尽可能独特的值：

  • 使用良好的散列函数，从而产生良好的分布
  • 使用适当的初始值来区分更多，以便 aPoint和 aLine返回相同哈希的机会变得更小。
于 2012-11-19T15:31:36.100 回答
0

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

例子：

//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 = h % 2^32;

所以：

h = (((ip  + a) * p + b) * p + c) % 2^32
  = (( ip² + ap     + b) * p + c) % 2^32
  = (  ip³ + ap²    + bp     + c) % 2^32
  = ip³ % 2^32 + (ap² + bp + c) % 2^32

因此，在这种情况下，初始值i将通过向哈希添加一个常量值以相同的方式影响所有哈希码i*p³ % 2^32。

于 2020-12-18T15:26:20.083 回答