为什么 GetHashCode 方法需要在 C# 中进行移位

Question

根据 MSDN GetHashCode 方法：

public struct Point
{
    private int x;
    private int y;

    public Point(int x, int y)
    {
       this.x = x;
       this.y = y;
    }

    public override bool Equals(Object obj)
    {
       if (!(obj is Point)) return false;

       Point p = (Point) obj;
       return x == p.x & y == p.y;
    }

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

    private int ShiftAndWrap(int value, int positions)
    {
        positions = positions & 0x1F;

        // Save the existing bit pattern, but interpret it as an unsigned integer.
        uint number = BitConverter.ToUInt32(BitConverter.GetBytes(value), 0);
        // Preserve the bits to be discarded.
        uint wrapped = number >> (32 - positions);
        // Shift and wrap the discarded bits.
        return BitConverter.ToInt32(BitConverter.GetBytes((number << positions) | wrapped), 0);
    }
}

我对 ShiftAndWrap 方法感到困惑，我知道它用于避免生成冲突哈希码。但我有以下疑问：

为什么参数positions设置为2？
为什么方法先右移 (32-positions) 然后左移 positons,有具体含义吗？
如前所述，此方法用于减少发生碰撞的情况，例如new Point(5,8) 与 new Point(8,5)，但是如果我创建一个像 new Point(3,16) 这样的对象，它将获得与 new Point(5,8) 相同的哈希码，所以.. . 这个方法的实际效果是什么？

Answer 1

HashCode的要点是创建一个分布，以便数据结构可以将数据分配到特定的桶中。它并不意味着平等。

如果查看 HashSet 的内部结构，您可以看到 class 使用 HashCode 来识别正确的桶，然后使用 Equals 方法确定平等。

    /// <summary>
    /// Checks if this hashset contains the item
    /// </summary>
    /// <param name="item">item to check for containment</param>
    /// <returns>true if item contained; false if not</returns>
    public bool Contains(T item) {
        if (m_buckets != null) {
            int hashCode = InternalGetHashCode(item);
            // see note at "HashSet" level describing why "- 1" appears in for loop
            for (int i = m_buckets[hashCode % m_buckets.Length] - 1; i >= 0; i = m_slots[i].next) {
                if (m_slots[i].hashCode == hashCode && m_comparer.Equals(m_slots[i].value, item)) {
                    return true;
                }
            }
        }
        // either m_buckets is null or wasn't found
        return false;
    }

所以碰撞很好，它就在那里，所以确保相对均匀的分布，以便更快地识别和检索。这意味着，在您的情况下，这两个点都将放在同一个桶中，但将使用它们的 Equals 方法来识别它们。

Answer 2

我不能说他们为什么选择这个特定的哈希码实现，但是关于这个问题：

Why the method do right-shift (32-positions) first then do left-shift positons, Does it have specific meaning?

此处的ShiftAndWrap()方法是一种算法的通用实现，用于将值左移N位并将溢出返回到末尾。所以在他们进行移位之前，他们首先得到最左边的 N 位，然后他们可以将它们附加到末尾。

如果我们只使用 8 位值 (bytes) 并使用 value = (binary) 11010010 调用 ShiftAndWrap() 和positions = 3:

value = 11010010

positions = 3

wrapped = value >> (8 - positions)
        = 11010010 >> (8 - 3) 
        = 11010010 >> 5 
        = 00000110

result = value << positions | wrapped
       = 11010010 << 3 | 00000110 
       = 10010000 | 00000110 
       = 10010110

我们可以看到return值10010110是将11010010移动三位并环绕结果的结果。

至于他们为什么不直接使用 x ^ y 的问题，我怀疑这是因为这意味着 Point(N, M) 总是会产生与 Point(M, N) 相同的哈希码.通过对 x 值进行移位，我们可以得到一个哈希码，它不仅考虑了 x 和 y 值，还考虑了它们的顺序，而 x ^ y会忽略他们的命令。

在对包含相同类型子组件的数据结构进行哈希处理时，通常让哈希函数以不同方式处理每个子组件，以便它们的位置很重要。例如，Java 对字符串使用此哈希公式（此处 ^ 表示指数，而不是 XOR）：

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

我们可以看到每个字符都乘以了不同的31次方，所以stop和pots有不同的哈希码。

至于他们为什么选择 2 作为要移动的位置数，这可能是任意的，或者他们可能已经做了一些评估以查看移动到什么程度可能会产生最佳分布。

为什么 GetHashCode 方法需要在 C# 中进行移位

Why GetHashCode method needs to do shift in C#

c#

gethashcode