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

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

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

我通常会采用 Josh Bloch 中给出的实现方式fabulous 有效的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稍后的例子，例如，我使用了显然运行良好的数字 - 但初始值不是素数。 （乘法常数is不过。我不太清楚这有多重要。）

这比通常的做法要好XOR计算哈希码有两个主要原因。假设我们有一个类型有两个int fields:

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：

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

链接到FNV文章已损坏，但这是互联网档案馆中的副本：永远困惑 - 哈希的艺术