如何在c#中对int[]进行哈希处理

Question

我正在尝试想出一种在调用Vector2[]时覆盖GetHashCode()的方法。这段代码为我知道相等的对象生成了非唯一的哈希值：我向以下类传递相同的矩形，但生成了不同的哈希码。

public Shape(Rectangle r)
        {
            edges = new Vector2[4];
            edges[0] = new Vector2(0, 0);
            edges[1] = new Vector2(r.Width, 0);
            edges[2] = new Vector2(r.Width, r.Height);
            edges[3] = new Vector2(0, r.Height);
            Console.Write(edges.GetHashCode() + "\n");
            Position = new Vector2(r.X, r.Y);                
        }

一个 Vector2 数组只是一堆整数。我该如何为整数列表创建唯一的哈希值？

- Max Kessler

---

这段代码应该可以工作。你能否发布一个完整的示例，展示两个相等的向量产生不同的哈希码？ - David Schwartz

数组不提供基于数组内容的哈希码，因此这段代码无法工作。你必须自己编写代码，或者如果你使用的是.NET 4，则可以使用IStructuralEquatable接口。 - Simon Whitehead

@SimonWhitehead：真的吗？那么Vector2.GetHashCode返回什么呢？ - David Schwartz

@DavidSchwartz Vector2实例的哈希值。但是edges.GetHashCode不会根据数组中每个Vector2实例生成哈希值。请注意，edges是一个Vector2数组。 - Simon Whitehead

@SimonWhitehead：哦！没错，发现得好。 - David Schwartz

Answer 1

您可以使用类似以下代码的方式实现此功能：

public static int CombineHashCodes(params int[] hashCodes)
{
    if (hashCodes == null)
    {
        throw new ArgumentNullException("hashCodes");
    }

    if (hashCodes.Length == 0)
    {
        throw new IndexOutOfRangeException();
    }

    if (hashCodes.Length == 1)
    {
        return hashCodes[0];
    }

    var result = hashCodes[0];

    for (var i = 1; i < hashCodes.Length; i++)
    {
        result = CombineHashCodes(result, hashCodes[i]);
    }

    return result;
}

private static int CombineHashCodes(int h1, int h2)
{
    return (h1 << 5) + h1 ^ h2;

    // another implementation
    //unchecked
    //{
    //    var hash = 17;

    //    hash = hash * 23 + h1;
    //    hash = hash * 23 + h2;

    //    return hash;
    //}
}

- Kirill Polishchuk

---

所以，它每次循环都会遍历一个数组的两个 int 值，携带一个总值，每次迭代都会将该值左移五位，并增加自己和下一个数字异或的结果。也许我不理解位移是如何工作的，但这样做不会产生一个极大的数字吗？最后我应该对我的哈希表的大小进行取模处理吗？无论如何，我认为这很有用。 - Max Kessler

不。它使用一个运行的“桶哈希”（h1与h2混合），因此其大小永远不会超过一个int，并且从末尾移位的位被丢弃。请记住，通常情况下，哈希值不是唯一的（也不能唯一）；它们必须稳定，并且希望分布良好。 - user166390

明白了！我修改了我的代码，不再使用碰撞作为识别两个对象是否相等的手段：我进行了一些研究，并重写了我的对象上的equals方法。非常感谢！ - Max Kessler