问快速简单的哈希码组合

EN

我个人要避免异或--这意味着任何两个相等的值都会导致0-所以散列(1，1) ==散列(2，2) ==散列(3，3)等等，也就是散列(5，0) ==散列(0，5)等等。我故意用它来设置散列--如果你想散列一系列商品，而你不关心订单，那就太好了。

我通常用：

unchecked
{
    int hash = 17;
    hash = hash * 31 + firstField.GetHashCode();
    hash = hash * 31 + secondField.GetHashCode();
    return hash;
}

这就是乔希·布洛赫在有效Java中建议的形式。上一次我回答一个类似的问题时，我找到了一篇详细讨论这一问题的文章-- IIRC，没有人真正知道它为什么工作得很好，但它确实有效。它也很容易记住，很容易实现，也很容易扩展到任意多个领域。

如果您正在使用.NET Core2.1或更高版本或.NET Framework4.6.1或更高版本，请考虑使用System.HashCode结构来帮助生成复合哈希代码。它有两种操作方式:添加和组合。

一个使用Combine的示例，它通常更简单，最多可用于八个项：

public override int GetHashCode()
{
    return HashCode.Combine(object1, object2);
}

使用Add的一个例子

public override int GetHashCode()
{
    var hash = new HashCode();
    hash.Add(this.object1);
    hash.Add(this.object2);
    return hash.ToHashCode();
}

优点：

• .NET本身的一部分，如.NET Core2.1/.NET标准2.1 (尽管，请参阅下面的con )
  • 对于.NET Framework4.6.1及更高版本，可以使用Microsoft.Bcl.HashCode NuGet包来支持这种类型。

• 基于作者和评审员在将其合并到corefx回购系统中之前所做的工作，看起来具有良好的性能和混合特性。
• 自动处理空
• 采用IEqualityComparer实例的重载

缺点：

• .NET框架在.NET 4.6.1之前不可用。HashCode是.NET标准2.1的一部分。截至2019年9月，.NET团队拥有没有计划在.NET框架上支持.NET标准2.1，名为.NET核心/ .NET 5是.NET的未来。
• 一般用途，所以它不会处理超级特定的情况以及手工编写的代码。

虽然Jon的答案中概述的模板作为一个散列函数族通常工作得很好，但常量的选择是很重要的，答案中提到的17的种子和31的因子对于普通用例根本不起作用。在大多数用例中，哈希值比int.MaxValue更接近于零，并且联合散列的项的数量是几十个或更少。

对于散列整数元组{x, y}，其中-1000 <= x <= 1000和-1000 <= y <= 1000，它的极差碰撞率几乎为98.5%。例如，{1, 0} -> {0, 31}、{1, 1} -> {0, 32}等，如果我们将覆盖范围扩大到包括3 <= n <= 25的n元组，那么它就不会那么糟糕了，碰撞率约为38%。但我们可以做得更好。

public static int CustomHash(int seed, int factor, params int[] vals)
{
    int hash = seed;
    foreach (int i in vals)
    {
        hash = (hash * factor) + i;
    }
    return hash;
}

我编写了一个蒙特卡罗抽样搜索循环，用不同的种子值和随机整数i的各种随机n元组上的因子测试了上述方法。允许的范围是2 <= n <= 25 ( n是随机的，但偏向于范围的低端)和-1000 <= i <= 1000。对每个种子和因子对进行了至少1200万次独特碰撞试验。

运行约7小时后，最佳结合点为：seed = 1009、factor = 9176，碰撞率为0.1131% (种子和因子均限制在4位以下)。在5位和6位数的区域，还有更好的选择。但为了简洁起见，我选择了前4位的表演者，它在所有常见的int和char散列场景中都表现得很好。它似乎也能很好地处理大得多的整数。

值得注意的是，作为种子和/或因素，“成为最佳”似乎并不是良好业绩的一般先决条件，尽管它可能有所帮助。上面提到的1009实际上是素数，但9176不是。在此，我显式地测试了各种变体，其中我将factor更改为9176附近的各种素数(同时离开了seed = 1009)，它们的性能都比上面的解决方案差。

最后，我还与一般的ReSharper推荐hash = (hash * factor) ^ i;函数族和上面提到的原始CustomHash()进行了比较，结果非常好。对于一般的用例假设，ReSharper XOR风格的碰撞率似乎在20-30%之间，我认为不应该使用。