为了账号安全,请及时绑定邮箱和手机立即绑定

快速简单的哈希码组合

/ 猿问

快速简单的哈希码组合

忽然笑 2019-12-25 11:17:30

人们能否推荐快速简单的方法来组合两个对象的哈希码。我没有太担心冲突,因为我有一个哈希表,该表可以有效地处理该问题,我只希望某些东西能够尽快生成代码。

围绕SO和Web进行阅读似乎有一些主要的候选人:

  1. 异或

  2. 使用素数乘法进行异或

  3. 简单的数字运算,例如乘法/除法(带有溢出检查或环绕)

  4. 生成一个String,然后使用String类的Hash Code方法

人们会推荐什么,为什么?


查看完整描述

3 回答

?
慕森王

我个人会避免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,没有人真正知道它为什么运作良好,但确实如此。它也很容易记住,易于实现,并且易于扩展到任意多个字段。


查看完整回答
反对 回复 2019-12-25
?
炎炎设计

尽管在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%的范围内,我认为不应使用。


查看完整回答
反对 回复 2019-12-25
?
qq_花开花谢_0

如果使用的是.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的未来。

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


查看完整回答
反对 回复 2019-12-25

添加回答

回复

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信