实现此复合GetHashCode()的最佳方法是什么

Question

我有一个简单的课程:

public class TileName {
    int Zoom, X, Y;

    public override bool Equals (object obj)
    {
        var o = obj as TileName;
        return (o != null) && (o.Zoom == Zoom) && (o.X == X) && (o.Y == Y);
    }

    public override int GetHashCode ()
    {
        return (Zoom + X + Y).GetHashCode();
    }
}

我很好奇,如果我做了类似的事情,我会得到更好的哈希码分布:

    public override int GetHashCode ()
    {
        return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode();
    }

这个类将被用作Dictionary键,所以我确实希望确保有一个不错的发行版.

Answer 1

就像Jon Skeet 在这个SO答案中所描述的那样,最佳做法是选择一些素数并将它们与单个哈希码相乘,然后将所有内容相加.

public int GetHashCode()
{
    unchecked
    {
        int hash = 17;
        // Maybe nullity checks, if these are objects not primitives!
        hash = hash * 23 + Zoom.GetHashCode();
        hash = hash * 23 + X.GetHashCode();
        hash = hash * 23 + Y.GetHashCode();
        return hash;
    }
}

xor哈希的问题是:

• 如果X等于Y那么你的哈希将只是缩放,因为然后X ^ Y = X ^ X = 0成立
• xor是对称操作时,会产生完全相同的散列为对象[Zoom = 3, X = 5, Y = 7],[Zoom = 3, X = 7, Y = 5],[Zoom = 7, X = 5, Y = 3]等.

这些事实使得xor方法更可能导致冲突.

除了Jons post之外,还可以考虑使用unchecked上下文来明确忽略溢出.因为像MSDN一样说:

如果既未使用也checked未unchecked使用,则常量表达式在编译时使用默认溢出检查,并进行检查.否则,如果表达式是非常量的,则运行时溢出检查取决于其他因素,例如编译器选项和环境配置.

因此,虽然通常会取消选中溢出,但在某些环境中或者使用某些编译器选项构建时,它可能会失败.但在这种情况下,您希望明确不检查这些溢出.

更新:

顺便说一下:someInt.GetHashCode()退货someInt.像这样,它当然是最快的,并且没有单一碰撞的完美哈希分布.你怎么把int映射到int-hash？:)所以我想说的是:你的第一种方法:

return (Zoom + X + Y).GetHashCode();

和你的第二个:

return Zoom.GetHashCode() + X.GetHashCode() + Y.GetHashCode();

完全一样.你甚至不必打电话GetHashCode,两者都很可能发生碰撞.xor如果您很可能对所有三个整数都有小整数值,那么可能比该方法更糟糕.

更新2:

正如我在ChaosPandions的评论中所写的那样:如果你只有这三个int值,并且X,Y并且Zoom是相对较小的数字(小于1000或10000),那么这个也可能是一个很好的哈希生成器:

public int GetHashCode()
{
    return (X << 16) ^ (Y << 8) ^ Zoom;
}

它只是分配哈希值中的位(以big-endian为例,以便于阅读):

00000000 00000000 00000011 00110001    X = 817
00000000 00000000 00011011 11111010    Y = 7162
00000000 00000000 00000010 10010110    Zoom = 662

00000011 00110001 00000000 00000000    X << 16
00000000 00011011 11111010 00000000    Y << 8
00000000 00000000 00000010 10010110    Zoom

00000011 00101010 11111000 10010110    (X << 16) ^ (Y << 8) ^ Zoom

Answer 2

你问题中的任何一个实现都不是理想的.例如,他们将返回完全相同的哈希值{ Zoom=1, X=2, Y=3 },{ Zoom=2, X=3, Y=1 },{ Zoom=3, X=1, Y=2 }等等等等.

我经常使用这样的东西:

public override int GetHashCode()
{
    // 269 and 47 are primes
    int hash = 269;
    hash = (hash * 47) + Zoom.GetHashCode();
    hash = (hash * 47) + X.GetHashCode();
    hash = (hash * 47) + Y.GetHashCode();
    return hash;
}

(从内存来看,我认为C#编译器在GetHashCode为匿名类型生成方法时会使用类似的东西.)

Answer 3

我实际上发现这真的很有效.

public override int GetHashCode ()
{
    return Zoom.GetHashCode() ^ X.GetHashCode() ^ Y.GetHashCode();
}

Answer 4

我知道这个问题有点老了，但现在你可以使用 System.HashCode 类轻松创建哈希码

https://docs.microsoft.com/en-us/dotnet/api/system.hashcode.combine?view=netcore-3.1

在这种特定情况下，它看起来像

public override int GetHashCode()
{
    return HashCode.Combine(Zoom, X, Y);
}