人们可以推荐快速简单的方法来组合两个对象的哈希码。我不太担心冲突,因为我有一个可以有效处理冲突的哈希表,我只想要尽快生成代码的东西。
阅读 SO 和网络似乎有几个主要的候选人:
- 异或
- 与素数乘法异或
- 简单的数字运算,例如乘法/除法(带有溢出检查或环绕)
- 构建一个字符串,然后使用字符串类的哈希码方法
人们会推荐什么,为什么?
我个人会避免异或 - 这意味着任何两个相等的值都会导致 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,没有人真正知道为什么它运作良好,但确实如此。它也易于记忆、易于实现,并且易于扩展到任意数量的字段。
如果您使用 .NET Core 2.1或更高版本或 .NET Framework 4.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();
}
优点:
IEqualityComparer
实例的重载缺点:
HashCode
是 .NET Standard 2.1 的一部分。截至 2019 年 9 月,.NET 团队没有计划在 .NET Framework 上支持 .NET Standard 2.1,因为.NET Core/.NET 5 是 .NET 的未来。虽然 Jon Skeet 的答案中概述的模板通常作为散列函数系列效果很好,但常数的选择很重要,并且答案中提到的种子17
和因子31
对于常见用例根本不起作用。在大多数用例中,散列值比 更接近于 0 int.MaxValue
,并且联合散列的项目数为几十个或更少。
对于散列一个整数元组{x, y}
where-1000 <= x <= 1000
和-1000 <= y <= 1000
,它的碰撞率几乎是 98.5%。例如,{1, 0} -> {0, 31}
,{1, 1} -> {0, 32}
等。如果我们将覆盖范围扩大到还包括 n 元组 where 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 位领域,存在更好的选择。int
但为了简洁起见,我选择了前 4 位数的表现,它在所有常见和char
散列场景中都表现得很好。它似乎也适用于更大数量的整数。
值得注意的是,“成为最佳人选”似乎并不是作为种子和/或因素获得良好表现的一般先决条件,尽管它可能会有所帮助。1009
上面提到的实际上是素数,但9176
不是。我明确测试了这方面的变化,我在附近(离开时)更改factor
为各种素数,它们的表现都比上述解决方案差。9176
seed = 1009
最后,我还与通用 ReSharper 推荐函数系列进行了比较,如上所述hash = (hash * factor) ^ i;
,原始推荐函数家族的性能明显优于它。CustomHash()
对于常见的用例假设,ReSharper XOR 样式的冲突率似乎在 20-30% 范围内,我认为不应该使用。
使用元组中的组合逻辑。该示例使用 c#7 元组。
(field1, field2).GetHashCode();
我认为 .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;
}
这是对Special Sauce精心研究的解决方案的重新包装。
它利用了值元组 ( ITuple
)。
这允许参数seed
和的默认值factor
。
public static int CombineHashes(this ITuple tupled, int seed=1009, int factor=9176)
{
var hash = seed;
for (var i = 0; i < tupled.Length; i++)
{
unchecked
{
hash = hash * factor + tupled[i].GetHashCode();
}
}
return hash;
}
用法:
var hash1 = ("Foo", "Bar", 42).CombineHashes();
var hash2 = ("Jon", "Skeet", "Constants").CombineHashes(seed=17, factor=31);
如果您的输入哈希大小相同,分布均匀且彼此不相关,则 XOR 应该没问题。再加上它很快。
我建议的情况是您想要做的
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 中的内置哈希函数,而不是自己滚动。