1

我有几个要放入哈希表的顶点。彼此非常接近的顶点被认为是同一个顶点。我的 C# 顶点类如下所示：

public class Vertex3D
{
    protected double _x, _y, _z;
    public static readonly double EPSILON = 1e-10;

    public virtual double x 
    {
        get { return _x;}
        set { _x = value; }
    }

    public virtual double y
    {
        get { return _y; }
        set { _y = value; }
    }

    public virtual double z
    {
        get { return _z; }
        set { _z = value; }
    }

    public Vertex3D(double p1, double p2, double p3)
    {
        this._x = p1;
        this._y = p2;
        this._z = p3;
    }

    public override bool Equals(object obj)
    {
        var other = obj as Vertex3D;

        if (other == null)
        {
            return false;
        }
        double diffx = this.x - other.x;
        double diffy = this.y - other.y;
        double diffz = this.z - other.z;
        bool eqx = diffx > -EPSILON && diffx < EPSILON;
        bool eqy = diffy > -EPSILON && diffy < EPSILON;
        bool eqz = diffz > -EPSILON && diffz < EPSILON;
        return eqx && eqy && eqz;
    }

    public override int GetHashCode()
    {
        return this.x.GetHashCode() ^ this.y.GetHashCode() ^ this.z.GetHashCode();
    }

    public override string ToString()
    {
        return "Vertex:" + " " + x + " " + y + " " + z;
    }

现在假设我将以下两个顶点放入字典中（字典是不允许空键的哈希表）：

    Dictionary<Vertex3D, Vertex3D> vertexList = new Dictionary<Vertex3D, Vertex3D>();
    Vertex3D v0 = new Vertex3D(0.000000000000000037842417475065449, -1,   0.00000000000000011646698526992202));
    Vertex3D v1 = new Vertex3D(0, -1, 0));
    vertexList.Add(v0, v0);
    vertexList.Add(v1, v1);

问题是我对equals和hashcode的实现是错误的。上述两个顶点被认为是相等的，因为彼此之间的距离小于 EPSILON。但他们不返回相同的哈希码。

如何正确实现equals和hashcode？

4

2 回答 2

1

通常，只有当它们都引用同一个对象时，可变事物引用才应该被认为是等效的。只有对不可变事物的引用才应该使用任何其他平等定义。如果Object包含虚函数以在两个引用由单独的对象持有的情况下测试等效性会很有帮助，这两个引用都不会将其引用暴露给任何可能改变它的东西。不幸的是，即使有效不可变实例的可变类型模式非常普遍（例如，几乎所有不可变集合都使用一个或多个可变类型对象，例如数组来保存它们的数据），但没有标准模式与它进行等效性测试。

如果要将顶点存储在字典中Object.Equals用于相等性测试，它应该是不可变类型。或者，您可以定义IEqualityComparer<T>与字典一起使用的自定义，但您应该知道，它Dictionary应该只用于查找完美匹配。如果您希望能够找到EPSILON给定点内的任何点，您应该使用将四舍五入的值映射到精确值列表的 a（值应该四舍五入到至少是 epsilon 的两倍的 2 次方）。如果从一个点的部分或全部坐标中添加或减去 EPSILON 会导致它以不同的方式四舍五入，则该点应包含在字典中，并以所有可能的方式四舍五入。

于 2013-07-11T16:54:45.547 回答
1

哈希表需要等价类，但你Equals()的不是传递的。因此，您不能为此目的使用哈希表。（例如，如果您允许附近的对象通过舍入到格点来比较相等，那么您将拥有传递性和等价类。但是仍然会有任意接近的点，直到您的表示精度，它们落在相反的两侧阈值，因此在不同的等价类中）

还有其他数据结构，例如八叉树，旨在加速寻找附近的点。我建议你使用其中之一。

于 2013-07-11T16:59:28.103 回答