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

在. NET System.Object.GetHashCode方法中，在整个. NET 基类库中使用很多地方。特别是在快速查找集合中的项目或确定相等性时。是否有关于如何为我的自定义类实现GetHashCode覆盖的标准算法 / 最佳实践，因此我不会降低性能？

答案

我通常会使用 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例子中，我使用的数字显然效果很好 - 但初始值不是素数。（乘法常数虽然是素数。我不知道它有多重要。）

由于两个主要原因，这比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：
您可以从不可变的字段计算哈希码; 要么
您可以确保在对象包含在依赖于其哈希代码的集合中时，可变对象的哈希码不会更改。

匿名类型

Microsoft 已经提供了一个很好的通用 HashCode 生成器：只需将属性 / 字段值复制到匿名类型并对其进行哈希：

new { PropA, PropB, PropC, PropD }.GetHashCode();

这适用于任意数量的属性。它不使用拳击。它只是使用框架中已经实现的匿名类型的算法。

ValueTuple - C＃7 的更新

正如 @cactuaroid 在评论中提到的，可以使用值元组。这节省了一些键击，更重要的是在堆栈上执行（没有垃圾）：

(PropA, PropB, PropC, PropD).GetHashCode();

（注意：使用匿名类型的原始技术似乎在堆上创建了一个对象，即垃圾，因为匿名类型是作为类实现的，尽管这可能会被编译器优化。对这些选项进行基准测试会很有趣，但是元组选项应该是优越的。）

这是我的哈希码助手。
它的优点是它使用泛型类型参数，因此不会导致装箱：

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            return 31 * hash + arg3.GetHashCode();
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, 
        T4 arg4)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            hash = 31 * hash + arg3.GetHashCode();
            return 31 * hash + arg4.GetHashCode();
        }
    }

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

它还有扩展方法来提供流畅的界面，所以你可以像这样使用它：

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

或者像这样：

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}