什么是2D点结构的适当`GetHashCode()`算法(避免冲突)

Question

请考虑以下代码:

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

Answer 1

乔恩双向飞碟有这个涵盖:

重写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,你可以让它做它的事情

Answer 2

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

如果可能的话,碰撞应该是罕见的,但它们并不意味着实施是不正确的.由于你给出的原因(高冲突),异或通常是不好的--Ohadsc已经发布了我之前给出的替代品样本,这应该没问题.

请注意,Vec2在没有碰撞的情况下实现是不可能的- 只有2 ^32个可能的返回值GetHashCode,但是有更多可能的X和Y值,即使你删除了NaN和无限值...

埃里克利珀有一个最近的一篇博客上GetHashCode,你可能会发现有用的.