快速和简单的哈希代码组合

人们可以推荐快速和简单的方法来组合两个对象的哈希代码。 我不太担心碰撞，因为我有一个哈希表，这将有效地处理我只是想尽快生成代码的东西。

围绕SO和networking来看，似乎有几个主要的候选人：

  1. 异或
  2. 与主乘法XORing
  3. 简单的数字操作，如乘/除（溢出检查或环绕）
  4. 构build一个String，然后使用String类的Hash Code方法

人们会推荐什么？为什么？

我个人会避免异或 – 这意味着任何两个相等的值将导致0 – 所以散列（1，1）=散列（2，2）=散列（3，3）等散列（5,0） ==散列（0，5）等可能偶尔出现。 我故意用它来设置哈希 – 如果你想散列一系列的项目，你不关心sorting，这是很好的。

我通常使用： 

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

这是Josh Bloch在Effective Java中提出的forms。 上次我回答了一个类似的问题，我设法find了一篇文章，详细讨论了这个问题–IIRC，没有人真正知道它为什么运作良好，但它确实如此。 这也很容易记住，易于实施，并易于扩展到任何领域。

尽pipeJon Skeet的答案中概述的模板作为一个散列函数族是很好的，但是常量的select很重要，在回答中提到的17和31因子对于常见的用例来说效果不好。 在大多数情况下，散列值比int.MaxValue更接近于零，并且联合散列的项数是几十个或更less。

对于其中-1000 <= x <= 1000和-1000 <= y <= 1000的整数元组{x, y}进行哈希处理，它具有近乎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; }

我写了一个蒙特卡洛采样search循环，用各种随机整数i随机n元组对种子和因子testing上面的方法。 允许的范围是2 <= n <= 25 （其中n是随机的，但是偏向该范围的下限）并且-1000 <= i <= 1000 。 每个种子和因子对至less进行了1200万次独特的碰撞试验。

运行约7小时后，find的最好的一对（种子和因子都限制在4位或更less）是： seed = 1009 ， factor = 9176 ，碰撞率为0.1131％。 在5位和6位数字领域，还有更好的select。 但是为了简洁起见，我select了顶尖的4位数表演者，并且在所有常见的int和char哈希情况下都performance得相当出色。 它似乎也可以用更大的整数工作得很好。

值得注意的是，作为种子和/或因素，尽pipe可能有所帮助，但“成为首要”似乎不是成为良好performance的一般先决条件。 上面提到的1009实际上是素数，但9176不是。 我明确地testing了这个变化，我在9176附近改变了各种素数（同时离开seed = 1009 ），他们都比上面的解决schemeperformance得更差。

最后，我还比较了hash = (hash * factor) ^ i;的genericsReSharper推荐函数族hash = (hash * factor) ^ i; 和上面提到的原始CustomHash()严重地胜过它。 ReSharper XOR风格在常见用例假设中的碰撞率似乎在20-30％范围内，不应该用在我看来。

我认为.NET框架团队在testing他们的System.String.GetHashCode（）实现方面做了不错的工作，所以我会使用它： 

 // System.String.GetHashCode(): http://referencesource.microsoft.com/#mscorlib/system/string.cs,0a17bbac4851d0d4 // System.Web.Util.StringUtil.GetStringHashCode(System.String): http://referencesource.microsoft.com/#System.Web/Util/StringUtil.cs,c97063570b4e791a public static int CombineHashCodes(IEnumerable<int> hashCodes) { int hash1 = (5381 << 16) + 5381; int hash2 = hash1; int i = 0; foreach (var hashCode in hashCodes) { if (i % 2 == 0) hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ hashCode; else hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ hashCode; ++i; } return hash1 + (hash2 * 1566083941); }

另一个实现是从System.Web.Util.HashCodeCombiner.CombineHashCodes（System.Int32，System.Int32）和System.Array.CombineHashCodes（System.Int32，System.Int32）方法。 这个比较简单，但可能没有上面的方法那么好： 

 // System.Web.Util.HashCodeCombiner.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#System.Web/Util/HashCodeCombiner.cs,21fb74ad8bb43f6b // System.Array.CombineHashCodes(System.Int32, System.Int32): http://referencesource.microsoft.com/#mscorlib/system/array.cs,87d117c8cc772cca public static int CombineHashCodes(IEnumerable<int> hashCodes) { int hash = 5381; foreach (var hashCode in hashCodes) hash = ((hash << 5) + hash) ^ hashCode; return hash; }

如果你正在寻找速度，并没有太多的碰撞，那么XOR是最快的。 为了防止在零附近聚集，你可以做这样的事情： 

 finalHash = hash1 ^ hash2; return finalHash != 0 ? finalHash : hash1;

当然，一些原型应该给你一个性能和集群的想法。

如果你的input哈希是相同的大小，均匀分布和彼此不相关，那么XOR应该是OK的。 加上它很快。

我build议这种情况是你想要做的 

 H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.

当然，如果A和B可以用合理的（不可忽略的）概率散列到相同的值，那么你不应该以这种方式使用XOR。

我会build议在System.Security.Cryptography中使用内置的散列函数，而不是滚动自己的。

Interesting Posts