人们可以推荐快速简单的方法来组合两个对象的哈希码。我并不太担心碰撞,因为我有一个Hash Table可以有效地处理这个问题我只想要尽可能快地生成代码的东西。
阅读SO和网络似乎有几个主要候选人:
人们会推荐什么?为什么?
我个人会避免异或 - 这意味着任何两个相等的值将导致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;
}
这就是Josh Bloch在Effective Java中提出的形式。上次我回答了类似的问题时,我设法找到了一篇文章,详细讨论了这个问题 - IIRC,没有人真正知道它为什么运作良好,但确实如此。它易于记忆,易于实现,并且易于扩展到任意数量的领域。
虽然Jon Skeet的答案中概述的模板通常作为哈希函数族很好用,但常量的选择很重要,并且答案中提到的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小时后,找到的最佳配对(种子和因子均限制在4位或以下)为:seed = 1009
,factor = 9176
,碰撞率为0.1131%。在5位和6位数区域,存在更好的选择。但为了简洁起见,我选择了前4位数的表演者,并且它在所有常见的int
和char
哈希场景中表现得非常好。它似乎也适用于更大幅度的整数。
值得注意的是,“成为主要”似乎并不是作为种子和/或因素的良好表现的一般先决条件,尽管它可能有所帮助。上面提到的1009
实际上是素数,但9176
不是。我明确地测试了这方面的变化,我将factor
改为9176
附近的各种素数(同时离开seed = 1009
)并且它们都比上述解决方案表现更差。
最后,我还与hash = (hash * factor) ^ i;
的通用ReSharper推荐函数系列进行了比较,如上所述,原始的CustomHash()
严重优于它。对于常见用例假设,ReSharper XOR样式的碰撞率似乎在20-30%范围内,不应该在我看来使用。
如果您使用的是.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();
}
优点:
IEqualityComparer
实例的重载缺点:
HashCode
是否会成为其中的一部分。我认为.NET Framework团队在测试他们的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;
}
在元组中使用组合逻辑。该示例使用c#7元组。
(field1, field2).GetHashCode();
如果您的输入哈希值相同,均匀分布且彼此不相关,那么异或应该是正常的。而且速度很快。
我建议的情况是你想要做的事情
H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.
当然,如果A和B可以预期以合理的(不可忽略的)概率散列到相同的值,那么就不应该以这种方式使用XOR。
如果您正在寻找速度并且没有太多碰撞,那么XOR是最快的。为了防止在零附近聚类,您可以执行以下操作:
finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;
当然,一些原型设计应该让你了解性能和聚类。
假设你有一个相关的toString()函数(你的不同字段出现),我只会返回它的哈希码:
this.toString().hashCode();
这不是很快,但应该避免碰撞。
我建议使用System.Security.Cryptography中的内置哈希函数,而不是自己编写。