一尘不染

覆盖 GetHashCode 的最佳算法是什么?

javascript

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

是否有关于如何GetHashCode为我的自定义类实现的标准算法或最佳实践,这样我就不会降低性能?


阅读 141

收藏
2022-02-22

共1个答案

一尘不染

我通常会使用类似于 Josh Bloch精彩的 Effective Java中给出的实现。它速度很快,并且创建了一个不太可能导致冲突的非常好的哈希。选择两个不同的素数,例如 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示例中,我使用了显然工作良好的数字 - 但初始值不是质数。(虽然乘法常数素数。我不知道这有多重要。)

这比XORing 哈希码的常见做法更好,主要有两个原因。假设我们有一个包含两个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:

  • 您可以从不可变的字段计算哈希码;要么
  • 您可以确保当对象包含在依赖于其哈希码的集合中时,可变对象的哈希码不会改变。
2022-02-22