一尘不染

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

algorithm

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

有没有关于如何GetHashCode为我的自定义类实现的标准算法或最佳实践,以免降低性能?


阅读 221

收藏
2020-07-28

共1个答案

一尘不染

我通常会使用类似于Josh Bloch _出色的_EffectiveJava中给出的实现的东西。它速度很快,并且创建了一个很好的哈希,不太可能导致冲突。选择两个不同的质数,例如17和23,然后执行:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

如评论中所述,您可能会发现最好选择一个大质数乘以。显然486187739是个好主意……尽管我看到的大多数带有小数的示例都倾向于使用质数,但至少有一些类似的算法经常使用非质数。例如,在稍后的非FNV示例中,我使用了看起来很有效的数字-
但初始值不是素数。(但是乘法常数 素数。我不知道它的重要性。)

这有XOR两个主要原因,它比哈希码的通用做法更好。假设我们有一个带有两个int字段的类型:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

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

此页面提供了很多选项。我认为,在大多数情况下,以上内容“足够好”,而且很难记住和正确使用。所述FNV替代方案是同样简单,但使用不同的常数和XOR代替ADD作为组合操作。它看起来
的东西
像下面的代码,但正常的FNV算法对每个字节进行操作,所以这将需要修改来执行的,而不是每32位的哈希值每字节一个迭代。FNV还设计用于可变长度的数据,而我们在这里使用它的方式始终是针对相同数量的字段值。对这个答案的评论表明,此处的代码实际上不如上面的添加方法那样工作(在测试的示例案例中)。

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

请注意,需要注意的一件事是,理想情况下,应在将其对等值敏感(因此对哈希码敏感)的状态添加到依赖于哈希码的集合中后,再进行更改。

根据文档

您可以覆盖GetHashCode以获取不可变的引用类型。通常,对于可变引用类型,仅在以下情况下才应覆盖GetHashCode:

  • 您可以从不可变的字段中计算哈希码;要么
  • 您可以确保在对象包含在依赖于其哈希代码的集合中时,该可变对象的哈希代码不会更改。
2020-07-28