此 GetHashCode 方法中的位移值如何改进散列？

Question

我在我正在处理的代码库中发现了两种具有哈希码方法的数据类型，我不完全理解为什么选择它们：

public override int GetHashCode()
{
    return x.GetHashCode() ^ y.GetHashCode() << 2;
}

public override int GetHashCode()
{
    return x.GetHashCode() ^ y.GetHashCode() << 2 ^ z.GetHashCode() >> 2;
}

移位操作如何使这些哈希值变得更好？

Answer 1

假设您有一个 Point 数据结构，由 x 和 y 变量表示。如果没有移位，(1,0) 的哈希码值将是 1，而 (0,1) 的哈希码也将是 1。现在对位移做同样的事情，对于 (1,0) 我们得到一个哈希码 1，但是对于 (0,1) 我们现在得到一个哈希码 4

移位提供的是，如果你有相同的输入但顺序不同，你想获得不同的哈希码，这样 (1,0) 和 (0,1) 就不会落入到相同的哈希桶并降低您的 hashset/dictionary 性能。

通常你会做一个比左移两次大得多的偏移量。如果处理接近 Int32.MaxValue 的哈希码，位移也会导致数据被截断。这是我通常使用的模式

public override int GetHashCode()
{
    unchecked
    {
        var hashCode = X;
        hashCode = (hashCode*397) ^ Y;
        hashCode = (hashCode*397) ^ Z;
        return hashCode;
    }
}

（这是 Resharper 的 "Insert Comparison Method" 功能附带的默认实现。要添加更多字段，您只需继续 hashCode = (hashCode*397) ^ XXXXXXX）

通过使用 * 和 unchecked 而不是 << 任何大于 Int32.MaxValue 的值都会溢出而不会出错。

此 GetHashCode 方法中的位移值如何改进散列？

How does bit shifting values in this GetHashCode method improve hashing?

c#

hash

bit-shift

gethashcode