这是一个学术观点,但是如果我不理解为什么有效的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
3),以相同的方式影响所有哈希码。 最佳答案
初始值必须是质数。为什么?因为您说要散列以获得长度为20的数组的索引:[object.getHash()%20]是要在其中存储对象的数组的索引。
如果您使用的是偶数:数据结构的一半地址将永远不会被使用...这就是为什么您需要使用初始值:最小化冲突...并最大程度地使用数据结构的原因