18

考虑以下代码：

struct Vec2 : IEquatable<Vec2>
{
    double X,Y;

    public bool Equals(Vec2 other)
    {
        return X.Equals(other.X) && Y.Equals(other.Y);
    }

    public override bool Equals(object obj)
    {
        if (obj is Vec2)
        {
            return Equals((Vec2)obj);
        }
        return false;
    }

    // this will return the same value when X, Y are swapped
    public override int GetHashCode()
    {
        return X.GetHashCode() ^ Y.GetHashCode();
    }

}

除了比较双精度值是否相等（这只是演示代码）之外，我关心的是交换 X、Y 值时会出现哈希冲突。例如：

Vec2 A = new Vec2() { X=1, Y=5 };
Vec2 B = new Vec2() { X=5, Y=1 };

bool test1 = A.Equals(B);  // returns false;
bool test2 = A.GetHashCode() == B.GetHashCode() // returns true !!!!!

这应该会破坏字典集合。所以问题是如何GetHashCode()为 2,3 甚至 4 个浮点值设置函数的属性，以使结果不对称并且散列不会发生冲突。

编辑1：

Point实施不适当的x ^ y解决方案，PointF并将ValueType.GetHashCode().

Rectangle哈希码有一个非常特殊的(((X ^ ((Y << 13) | (Y >> 19))) ^ ((Width << 26) | (Width >> 6))) ^ ((Height << 7) | (Height >> 25)))表达式，似乎按预期执行。

编辑2：

'System.Double' 有一个很好的实现，因为它并不认为每一位都同等重要

public override unsafe int GetHashCode() //from System.Double
{
    double num = this;
    if (num == 0.0)
    {
        return 0;
    }
    long num2 = *((long*) &num);
    return (((int) num2) ^ ((int) (num2 >> 32)));
}
4

5 回答 5

21

Jon skeet 涵盖了以下内容：

覆盖 System.Object.GetHashCode 的最佳算法是什么？

   public override int GetHashCode()
   {
       unchecked // Overflow is fine, just wrap
       {
           int hash = 17;
           // Suitable nullity checks etc, of course :)
           hash = hash * 23 + X.GetHashCode();
           hash = hash * 23 + Y.GetHashCode();
           return hash;
       }
   }

此外，将您的Equals(object)实现更改为：

return Equals(obj as FVector2);

但是请注意，这可能会认为派生类型是相等的。如果您不希望这样，则必须将运行时类型other.GetType()与typeof(FVector2)（并且不要忘记空值检查）进行比较 感谢您指出它是一个结构，LukH

Resharper 为相等和哈希码生成了很好的代码，所以如果你有 resharper，你可以让它做它的事情

于 2011-03-07T15:22:11.997 回答
7

哈希冲突不会对字典集合造成严重破坏。如果你不幸得到它们，它们会降低效率，但字典必须应对它们。

如果可能的话，冲突应该很少见，但这并不意味着实现不正确。由于您给出的原因（高冲突），XOR 通常很糟糕 - ohadsc 发布了我之前给出的替代示例，这应该没问题。

Vec2请注意，在没有冲突的情况下实现是不可能的——只有 2 32 个可能的返回值来自GetHashCode，但是有更多可能的 X 和 Y 值，即使在您删除了 NaN 和无限值之后......

Eric Lippert最近有一篇博文GetHashCode，您可能会发现它很有用。

于 2011-03-07T15:27:08.273 回答
1

坐标的合理范围是多少？

除非它可以是所有可能的整数值，否则您可以简单地：

常量 SOME_LARGE_NUMBER=100000; 返回 SOME_LARGE_NUMBER * x + y；

于 2011-03-07T15:33:04.463 回答
0

如果哈希码的大小小于结构的大小，那么无论如何冲突都是不可避免的。

于 2011-03-07T15:27:11.283 回答
0

哈希码方法适用于整数坐标，但不推荐用于浮点值。使用浮点坐标，可以通过使用排序的序列结构来创建点集/池。

排序序列是叶子版本的平衡二叉树。

这里的键是点坐标。

于 2015-01-08T02:46:01.883 回答