.net - 覆盖 GetHashCode 的最佳算法是什么？

Question

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

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

Answer 1

我通常采用类似 Josh Bloch 的fabulous 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稍后举例，例如，我使用的数字显然效果很好——但初始值不是质数。 (乘法常数 是 质数。我不知道它有多重要。)

这优于 XOR 哈希码的常见做法，主要有两个原因。假设我们有一个包含两个 int 字段的类型:

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

顺便说一句，早期的算法是 C# 编译器当前用于匿名类型的算法。

This page提供了很多选择。我认为在大多数情况下，上述内容“足够好”并且非常容易记住和正确。 FNV alternative 同样简单，但使用不同的常量和 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;
    }
}

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

根据 documentation :

You can override GetHashCode for immutable reference types. In general, for mutable reference types, you should override GetHashCode only if:

• You can compute the hash code from fields that are not mutable; or
• You can ensure that the hash code of a mutable object does not change while the object is contained in a collection that relies on its hash code.

FNV 的链接文章已损坏，但互联网文件馆中有一份副本:Eternally Confuzzled - The Art of Hashing