实现此复合 GetHashCode() 的最佳方法是什么 [英] What is the best way to implement this composite GetHashCode()

问题描述

我有一个简单的类:

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();
    }
}

我很好奇，如果我改为执行以下操作，是否会获得更好的哈希码分布:

I was curious if I would get a better distribution of hash codes if I instead did something like:

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

这个类将用作字典键，所以我想确保有一个合适的分布.

This class is going to be used as a Dictionary key, so I do want to make sure there is a decent distribution.

推荐答案

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

Like described by Jon Skeet in this SO answer, it is best practice to pick some prime numbers and multiply these with the single hash codes, then sum everything up.

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 那么你的哈希值就是 Zoom，因为 X ^ Y = X ^ X = 0 成立
• xor 是一个对称运算符，它将为对象生成完全相同的哈希值 [Zoom = 3, X = 5, Y = 7], [Zoom = 3, X = 7, Y = 5], [Zoom = 7, X = 5, Y = 3] 等

• if X is equal to Y then your hash will be just Zoom, because then X ^ Y = X ^ X = 0 holds
• xor is a symmetric operator, it will produce the exact same hashes for the objects [Zoom = 3, X = 5, Y = 7], [Zoom = 3, X = 7, Y = 5], [Zoom = 7, X = 5, Y = 3] etc.

这些事实使异或方法更容易引起冲突.

These facts make the xor-method more likely to cause collisions.

除了 Jons 的帖子，考虑使用 unchecked 上下文，以明确忽略溢出.因为就像 MSDN 说:

In addition to Jons post, consider using a unchecked context, for explicitly ignoring overflows. Because like the MSDN says:

如果 checked 和 unchecked 都不是used，常量表达式使用编译时的默认溢出检查时间，这是检查.否则，如果表达式是非常量的，运行时溢出检查取决于其他因素，例如编译器选项和环境配置.

If neither checked nor unchecked is used, a constant expression uses the default overflow checking at compile time, which is checked. Otherwise, if the expression is non-constant, the run-time overflow checking depends on other factors such as compiler options and environment configuration.

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

So while usually overflows will be unchecked, it may be that it fails somewhen in some environment or built with some compiler option. But in this case you want to explicitly not check these overflows.

更新:

顺便说一下:someInt.GetHashCode() 返回 someInt.像这样，它当然是最快的和完美的散列分布，没有单次冲突.你还会如何将 int 映射到 int-hash?:) 所以我想说的是:你的第一种方法:

By the way: someInt.GetHashCode() returns someInt. Like this, it is of course the fastest possible and a perfect hash distribution without a single collision. How else would you map an int to an int-hash? :) So what I wanted to say: Your first approach:

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

和你的第二个:

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

完全一样.您甚至不必调用 GetHashCode 并且两者很可能发生冲突.可能比 xor 方法更糟糕，如果您很可能对所有三个整数都有小整数值.

are exactly the same. You dont even have to call GetHashCode and both are very likely to have collisions. Maybe even worse than the xor method, if you very likely have small integer values for all three ints.

更新 2:

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

As I wrote in the comment to ChaosPandions post: If you just have those three int values, and X, Y and Zoom are relatively small numbers (smaller than 1000 or 10000) this one may be also a good hash generator:

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

它只是分配散列值中的位(例如为了可读性，在大端中):

It just distributes the bits in the hash value (example in big-endian for readability):

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

这篇关于实现此复合 GetHashCode() 的最佳方法是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！