12

众所周知，比较浮点数==通常是一个错误。在我写的一个 3D 向量类（带有浮点分量 X、Y、Z）中，如果两个向量的距离被认为为零，则它们被认为是相等的。

public override bool Equals(object obj)
{
    if (obj == null) {
        return false;
    }

    if (GetType () != obj.GetType ()) {
        return false;
    }

    float d = DistSq ((Vec) obj);

    return IsConsideredZero (d);
}

public float DistSq(Vec p)
{
    Vec d = this - p;
    return d.LengthSq ();
}

public float LengthSq()
{
    return X * X + Y * Y + Z * Z;
}

private const float VEC_COMPARE_EPSILON_ABS = 1E-05f;
public static bool IsConsideredZero(float f)
{
    return Math.Abs (f) < VEC_COMPARE_EPSILON_ABS;
}

到目前为止，一切正常。但是，现在我想获得向量的哈希码。我可以看到类似hash = (int)X^(int)Y^(int)Z的东西一定会失败。

我能想到的最好的办法是：

public override int GetHashCode()
{
    return 0;
}

当然，这有点糟糕。有什么方法可以获得合理的哈希码？NaN 和其他特殊值是可能的，但不太可能，如果这很重要的话。

4

5 回答 5

15

假设您想要拥有正常的哈希码/相等属性是不可能的：

  • 如果 X = Y 且 Y = Z 则 X = Z（传递性）
  • 如果 X = Y 则 Y = X（交换性）
  • X = X 对于所有 X（自反性）

第一条规则是问题 - 因为如果每个值都被视为“等于”下一个更大的可表示数字，那么最终所有数字都相等。例如，假设一个数字被认为等于另一个它们在 0.1 以内：

0 等于 0.08 0.08 等于 0.16 0.16 等于 0.24

=> 0 等于 0.16 通过传递性规则 => 0 等于 0.24 通过传递性规则

（ETC）

如果您忽略传递性规则，那么您仍然（可能）希望“相等”值具有相等的哈希码。这有效地执行了传递性规则——在上面的例子中，0 和 0.08 必须具有相等的哈希码，0 和 0.16 也是如此。因此 0 和 0.16 必须具有相同的哈希码，依此类推。因此你不能有有用的哈希码——它必须是一个常数。

于 2009-02-24T08:27:55.793 回答
8

我不认为你可以有一个与你的比较方法一致的哈希码，因为后者是不传递的：对于任何三个向量 A、B、C，如果A.Equals(B)和B.Equals(C)为真，它仍然可能A.Equals(C)是假的。（想象一下，如果 A 和 B 之间的距离是 6e-6，B 和 C 之间是 6e-6，A 和 C 之间是 1.2e-5）但是哈希码的相等性总是传递的，因为它们只是数字。

在这种情况下，我将创建一个 hashcode 方法，该方法根据浮点坐标的确切值计算哈希，并在文档中提到它与 equals 不一致。我知道这不是一个真正的解决方案，但鉴于我认为不存在真正的解决方案，拥有一个非平凡的哈希码比只有 0 更好。

于 2009-02-24T08:28:24.047 回答
7

恐怕不是一般情况。一个证明的草图是这样的：

取任意两个数 a 和 b。让它们之间的差异为d。然后，如果您创建 d/epsilon 数字，其间有一个 epsilon 步骤，则每个步骤必须与之前的步骤“相等”，根据哈希码语义，它具有相同的哈希码。所以所有数字必须具有相同的哈希码。

只有添加其他约束才能解决此问题。

顺便说一句，您对 Equals 的定义也是错误的，因为 a.Equals(b) 和 b.Equals(c) 可能是真的，而不是 a.Equals(c)，这对于 equals 是错误的。这被称为破坏传递性属性。

那我能做什么？

解决方案取决于您使用哈希的目的。一种解决方案是引入概念网格。更改等号和哈希码，如果在同一个网格立方体中，两个数字相等，方法是四舍五入到固定的小数位数，然后对四舍五入的数字取等于和哈希码。如果接近零是一个重要的情况，请在舍入前添加 epsilon/2 的偏移量，因此零是立方体的中心。这是正确的，但是您可以让两个数字任意靠近（在浮点数的限制下）而不相等。因此，对于某些应用程序来说会没问题，而其他应用程序则不会。这类似于mghie的一个想法。

于 2009-02-24T08:27:56.107 回答
4

每个人都是正确的...

然而，经常做的一件事是稍微扩展散列的概念。考虑一个带有边 >> epsilon 的盒子的 3d 空间分区。

一个点的哈希是它所属的盒子。当您想查找一个点时，您不会使用相应的框检查该点（就像您对常规散列所做的那样），而是检查相邻的框。在 3d 中，您最多可以使用 8 个盒子。

于 2009-02-24T08:48:42.170 回答
2

无论你使用什么技术都会有问题，因为你提出了一些无法解决的问题。

你想要的是 1) 均匀分布的散列，这样对于大多数数字 a 和 b 其中 a != b 然后 a.GetHashCode() != b.GetHashCode() 但是 2) 其中 a == b 然后 a.GetHashCode() = = b.GetHashCode() 必须为真。

返回一个常数满足 (2) 但不满足 (1)。

您可以证明在 1E-5 边界处舍入并将其用作散列违反了 (1) 但违反了 (2)。以 1E-5 和 2E-5 为例。四舍五入会产生两个不同的哈希值，但它们比较相等。这违反了上面的约束 (2)。你可以很容易地概括这一点，以证明任何数字的四舍五入都会遇到类似的问题。

我建议您选择不同的方法。我认为潜在的问题是确定某个点是否接近您已经拥有的点。我建议将坐标空间一分为二（沿边界的点（即距离边界 <=1E-5）在两半中）。如果您逐步划分空间（想想二叉树），您可以构建一个数据结构，该结构将快速返回您想要的结果并且相当容易构建。

如果我错过了我的猜测并且您必须使用散列，那么可以使用两个散列值执行您想要的操作，每个散列值四舍五入到 1E-5 但偏移 5E-6。所有相等的点将在两个哈希值之一上比较相等。这将要求您在哈希表中输入点两次，每个哈希例程一次。

于 2009-02-24T09:18:52.567 回答