快速简单的哈希码组合

Question

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

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

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

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

Answer 1

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

Answer 2

虽然乔恩斯基特的回答中列出的模板,一般工作以及哈希函数族,常数的选择是很重要的种子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%范围内,不应该在我看来使用.

Answer 3

如果您使用的是.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本身的一部分(但请参阅下面的内容)
• 根据作者和评论者在将其合并到corefx repo之前所做的工作,看起来具有良好的性能和混合特性
• 自动处理空值
• IEqualityComparer实例的重载

缺点:

• 截至2018年8月,仅在针对.NET Core 2.1时可用
  • 我假设这将慢慢进入.NET标准,然后进入各种其他实现.我不知道何时会发生这种情况.
• 通用,因此它不会处理超级特定情况以及手工制作的代码

Answer 4

我假设.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;
}

Answer 5

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

(field1, field2).GetHashCode();