快速简单的哈希码组合

Question

人们能否推荐快速简单的方法来组合两个对象的哈希码。我没有太担心冲突，因为我有一个哈希表，该表可以有效地处理该问题，我只希望某些东西能够尽快生成代码。围绕SO和Web进行阅读似乎有一些主要的候选人：异或使用素数乘法进行异或简单的数字运算，例如乘法/除法（带有溢出检查或环绕）生成一个String，然后使用String类的Hash Code方法人们会推荐什么，为什么？

Answer 1

我个人会避免XOR-这意味着任何两个相等的值都将导致0-因此hash（1，1）== hash（2，2）== hash（3，3）等。另外hash（5，0） == hash（0，5）等可能偶尔出现。我已经刻意用它集合散列-如果你想哈希项目的顺序，你不关心的排序，这是不错的。

我通常使用：

unchecked

{

    int hash = 17;

    hash = hash * 31 + firstField.GetHashCode();

    hash = hash * 31 + secondField.GetHashCode();

    return hash;

}

这就是Josh Bloch在Effective Java中建议的形式。上次回答类似的问题时，我设法找到了一篇文章进行了详细讨论-IIRC，没有人真正知道它为什么运作良好，但确实如此。它也很容易记住，易于实现，并且易于扩展到任意多个字段。

Answer 2

尽管在Jon Skeet的答案中概述的模板通常可以很好地作为哈希函数系列使用，但是常量的选择很重要，答案中指出的种子17和因数31对于普通用例来说根本无法正常工作。在大多数使用情况下，散列的值比都更接近于零int.MaxValue，并且共同进行散列的项目数不超过几十个。

对于散列一个整数的元组{x, y}，其中-1000 <= x <= 1000和-1000 <= y <= 1000，它有将近98.5％的深不可测的碰撞率。例如{1, 0} -> {0, 31}，{1, 1} -> {0, 32}等等。如果我们扩大覆盖范围还包括n元组在那里3 <= n <= 25，但它确实不太可怕的约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;

}

我写了一个蒙特卡洛采样搜索循环，用随机种子的各个随机n元组的各种种子和因子值测试了上述方法i。允许的范围为2 <= n <= 25（其中n为随机范围，但偏向范围的下限）和-1000 <= i <= 1000。每个种子和因子对至少进行了1200万次唯一的碰撞测试。

运行大约7小时后，最好对发现（其中种子和因子均被限制为4位数字或更少）为：seed = 1009，factor = 9176，用0.1131％的碰撞率。在5位和6位数字区域，甚至存在更好的选择。但是为了简洁起见，我选择了性能最高的4位数字，并且在所有常见int和char哈希情况下，它的表现都很好。对于更大的整数，它似乎也可以正常工作。

值得注意的是，“成为主要人物”似乎并不能作为取得种子和/或因素良好表现的一般先决条件，尽管它可能会有所帮助。1009上面提到的实际上是素数，但9176不是。我明确测试了这种变化，在factor附近9176（离开seed = 1009）更改为各种素数，它们的表现都比上述解决方案差。

最后，我还对比了通用的ReSharper推荐功能系列hash = (hash * factor) ^ i;和CustomHash()上面提到的原始功能严重胜过它。对于常见的用例假设，ReSharper XOR样式的冲突率似乎在20％至30％的范围内，我认为不应使用。

Answer 3

如果使用的是.NET Core 2.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 Core 2.1 / .NET Standard 2.1开始的.NET本身的一部分（尽管请参阅下面的con）

根据作者和审阅者在合并到corefx存储库中之前所做的工作，看起来具有良好的性能和混合特性。

自动处理空值

需要IEqualityComparer实例的重载

缺点：

在.NET Framework上不可用。HashCode是.NET Standard 2.1的一部分，但截至2019年9月，.NET团队尚无计划在.NET Framework上支持.NET Standard，因为.NET Core / .NET 5是.NET的未来。

通用，因此将无法处理超特定情况以及手工编写的代码