这是一个学术观点,但我觉得如果我不理解为什么这会被诸如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()]是你想要存储对象的数组的索引. 如果您使用了偶数:数据结构的一半地址将永远不会被使用…这就是您需要使用初始值的原因:最小化冲突…并最大化数据结构使用