快速简单的哈希码组合

问题描述 投票:51回答:9

人们可以推荐快速简单的方法来组合两个对象的哈希码。我并不太担心碰撞,因为我有一个Hash Table可以有效地处理这个问题我只想要尽可能快地生成代码的东西。

阅读SO和网络似乎有几个主要候选人:

  1. 异或
  2. 使用Prime乘法进行异或
  3. 简单的数字运算,如乘法/除法(溢出检查或环绕)
  4. 构建一个String然后使用String类的Hash Code方法

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

c# algorithm hash hashcode
9个回答
105
投票

我个人会避免异或 - 这意味着任何两个相等的值将导致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,没有人真正知道它为什么运作良好,但确实如此。它易于记忆,易于实现,并且易于扩展到任意数量的领域。


39
投票

虽然Jon Skeet的答案中概述的模板通常作为哈希函数族很好用,但常量的选择很重要,并且答案中提到的1731因子的种子在常见用例中根本不能很好地工作。在大多数用例中,散列值比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 = 1009factor = 9176,碰撞率为0.1131%。在5位和6位数区域,存在更好的选择。但为了简洁起见,我选择了前4位数的表演者,并且它在所有常见的intchar哈希场景中表现得非常好。它似乎也适用于更大幅度的整数。

值得注意的是,“成为主要”似乎并不是作为种子和/或因素的良好表现的一般先决条件,尽管它可能有所帮助。上面提到的1009实际上是素数,但9176不是。我明确地测试了这方面的变化,我将factor改为9176附近的各种素数(同时离开seed = 1009)并且它们都比上述解决方案表现更差。

最后,我还与hash = (hash * factor) ^ i;的通用ReSharper推荐函数系列进行了比较,如上所述,原始的CustomHash()严重优于它。对于常见用例假设,ReSharper XOR样式的碰撞率似乎在20-30%范围内,不应该在我看来使用。


24
投票

如果您使用的是.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();
}

优点:

缺点:

  • 截至2018年8月,仅在针对.NET Core 2.1或更高版本时可用。 截至2019年4月,部分.NET Standard 2.1 Preview。我不知道何时发布.NET Standard 2.1 Preview,我不确定HashCode是否会成为其中的一部分。
  • 通用,因此它不会处理超级特定情况以及手工制作的代码

16
投票

我认为.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;
}

7
投票

在元组中使用组合逻辑。该示例使用c#7元组。

(field1, field2).GetHashCode();

0
投票

如果您的输入哈希值相同,均匀分布且彼此不相关,那么异或应该是正常的。而且速度很快。

我建议的情况是你想要做的事情

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

当然,如果A和B可以预期以合理的(不可忽略的)概率散列到相同的值,那么就不应该以这种方式使用XOR。


0
投票

如果您正在寻找速度并且没有太多碰撞,那么XOR是最快的。为了防止在零附近聚类,您可以执行以下操作:

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

当然,一些原型设计应该让你了解性能和聚类。


0
投票

假设你有一个相关的toString()函数(你的不同字段出现),我只会返回它的哈希码:

this.toString().hashCode();

这不是很快,但应该避免碰撞。


-10
投票

我建议使用System.Security.Cryptography中的内置哈希函数,而不是自己编写。

© www.soinside.com 2019 - 2024. All rights reserved.