题
人们可以推荐快速而简单的方法来组合两个对象的哈希码吗?我不太担心冲突,因为我有一个哈希表,它可以有效地处理冲突,我只想要能够尽快生成代码的东西。
阅读 SO 和网络似乎有几个主要候选者:
- 异或运算
- 与素数乘法进行异或运算
- 简单的数字运算,如乘法/除法(带有溢出检查或环绕)
- 构建一个字符串,然后使用字符串类的哈希码方法
人们会推荐什么以及为什么?
解决方案
我个人会避免 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,没有人真正知道为什么它效果很好,但它确实如此。它还易于记忆、易于实施,并且易于扩展到任意数量的领域。
其他提示
虽然 Jon Skeet 的答案中概述的模板通常作为哈希函数系列运行良好,但常量的选择很重要,并且 17
和因数 31
正如答案中所述,对于常见用例来说根本不起作用。在大多数用例中,哈希值比零更接近于 int.MaxValue
, ,并且联合散列的项数为几十个或更少。
用于散列整数元组 {x, y}
在哪里 -1000 <= x <= 1000
和 -1000 <= y <= 1000
, ,它的碰撞率几乎高达 98.5%。例如, {1, 0} -> {0, 31}
, {1, 1} -> {0, 32}
, , ETC。如果我们将覆盖范围扩大到也包括 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% 范围内,我认为不应使用。
如果您使用的是.NET 核心2.1, ,考虑使用 系统哈希码 struct 来帮助生成复合哈希码。它有两种操作模式:添加并合并。
一个使用的例子 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 本身的一部分(不过,请参阅下面的反面)
- 根据作者和审稿人之前所做的工作,看起来具有良好的性能和混合特性 将其合并到 corefx 存储库中
- 自动处理空值
- 需要的重载
IEqualityComparer
实例
缺点:
- 截至 2018 年 8 月,仅在面向 .NET Core 2.1 或更高版本时可用。
- 截至 2019 年 4 月,.NET Standard 2.1 预览版的一部分。我不知道 .NET Standard 2.1 Preview 何时发布,也不确定是否会发布
HashCode
将是其中的一部分。
- 截至 2019 年 4 月,.NET Standard 2.1 预览版的一部分。我不知道 .NET Standard 2.1 Preview 何时发布,也不确定是否会发布
- 通用,因此它不能处理超级特定的情况以及手工编写的代码
我认为 .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();
如果您的输入哈希大小相同、分布均匀且彼此不相关,则 XOR 应该没问题。而且速度很快。
我建议的情况就是你想做的
H = hash(A) ^ hash(B); // A and B are different types, so there's no way A == B.
当然,如果可以预期 A 和 B 以合理(不可忽略)的概率散列到相同的值,那么您不应该以这种方式使用 XOR。
如果您追求速度并且没有太多冲突,那么异或是最快的。为了防止在零附近聚集,你可以这样做:
finalHash = hash1 ^ hash2;
return finalHash != 0 ? finalHash : hash1;
当然,一些原型设计应该能让您了解性能和集群。
假设您有一个相关的 toString() 函数(其中应出现不同的字段),我将只返回其哈希码:
this.toString().hashCode();
这不是很快,但应该可以很好地避免碰撞。
我建议使用 System.Security.Cryptography 中的内置哈希函数,而不是自行构建。