什么是适合2D点结构的`GetHashCode（）`算法（避免碰撞）

请考虑以下代码：

struct Vec2 : IEquatable { 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 !!!!! 

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

编辑1：

Point实现了不合适的x ^ y解决方案， PointF包装了ValueType.GetHashCode() 。

Rectangle有一个非常特殊的(((X ^ ((Y <> 19))) ^ ((Width <> 6))) ^ ((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 不会发生冲突是不可能的 – GetHashCode只有2 ^32个可能的返回值，但即使你删除了NaN和无限值，也有更多可能的X和Y值……

Eric Lippert 最近发表了一篇关于GetHashCode 博客文章 ，您可能会发现它很有用。

Answer 3

坐标的合理界限是什么？

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

const SOME_LARGE_NUMBER = 100000; 返回SOME_LARGE_NUMBER * x + y;

Answer 4

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

Answer 5

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

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

这里的键是点坐标。