重写GetHashCode的最佳算法是什么?

在.NET中,GetHashCode方法在.NET基类库的许多地方都使用。正确地实现它对于在集合中快速查找项或在确定相等性时尤为重要

对于如何为我的自定义类实现GetHashCode,从而不降低性能,是否有标准算法或最佳实践

我通常使用类似于Josh Bloch的出色的高效Java中给出的实现。它的速度很快,并且创建了一个非常好的散列,不太可能导致冲突。选择两个不同的素数,例如17和23,然后执行以下操作:

公共覆盖int GetHashCode()
{
未选中//溢出很好,只需换行
{
int hash=17;
//适当的空值检查等,当然:)
hash=hash*23+field1.GetHashCode();
hash=hash*23+field2.GetHashCode();
hash=hash*23+field3.GetHashCode();
返回散列;
}
}

正如在评论中所指出的,您可能会发现最好选择一个大的素数乘以。显然486187739很好。。。虽然我看到的大多数小数字的例子都倾向于使用素数,但至少有一些类似的算法经常使用非素数。例如,在后面的不完全是FNV的例子中,我使用了显然效果很好的数字——但初始值不是素数。(不过乘法常数是素数。我不知道这有多重要。)

由于两个主要原因,这比通常的异或散列代码的做法要好。假设我们有一个包含两个int字段的类型:

XorHash(x,x)==XorHash(y,y)==0表示所有x,y
XorHash(x,y)=XorHash(y,x)表示所有x,y

顺便说一下,早期的算法是C#编译器目前用于匿名类型的算法

本页提供了许多选项。我认为在大多数情况下,上述情况是;“够好了”;而且它非常容易记住和纠正。FNV替代方法同样简单,但使用不同的常量和XOR而不是ADD作为组合操作。它看起来像下面的代码,但是普通的FNV算法是对单个字节进行操作的,因此这需要修改以对每个字节执行一次迭代,而不是对每个32位哈希值执行一次迭代。FNV也是为可变长度的数据而设计的,而我们在这里使用它的方式总是针对相同数量的字段值。对这个答案的评论表明,这里的代码实际上并不像上面的加法方法那样有效(在测试的示例案例中)

//注意:不完全是FNV!
公共覆盖int GetHashCode()
{
未选中//溢出很好,只需换行
{
int散列=(int)2166136261;
//适当的空值检查等,当然:)
哈希=(哈希*16777619)^field1.GetHashCode();
哈希=(哈希*16777619)^field2.GetHashCode();
哈希=(哈希*16777619)^field3.GetHashCode();
返回散列;
}
}

请注意,需要注意的一点是,理想情况下,在将相等敏感(因此也是哈希代码敏感)状态添加到依赖于哈希代码的集合后,应该防止其发生更改

根据文件:

您可以覆盖不可变引用类型的GetHashCode。通常,对于可变引用类型,只有在以下情况下才应重写GetHashCode:

  • 您可以从不可变的字段计算哈希代码;或
  • 当可变对象包含在依赖其哈希代码的集合中时,可以确保该对象的哈希代码不会更改

FNV文章的链接已断开,但互联网档案中有一个副本:永远混乱——散列的艺术

发表评论