c# – 哈希码非零初始值 – 注意:我不是在询问素数

前端之家收集整理的这篇文章主要介绍了c# – 哈希码非零初始值 – 注意:我不是在询问素数前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
这是一个学术观点,但我觉得如果我不理解为什么这会被诸如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 * p3.

解决方法

初始值必须是素数.为什么?因为你要哈希来获取长度为20的数组的索引:[object.getHash()]是你想要存储对象的数组的索引. 如果您使用了偶数:数据结构的一半地址将永远不会被使用…这就是您需要使用初始值的原因:最小化冲突…并最大化数据结构使用

猜你在找的C#相关文章