有没有办法用 epsilon 获取浮点数的哈希码？

StackOverflow https://stackoverflow.com/questions/580905

  •  06-09-2019
  •  | 
  •  

题

众所周知，通过 == 比较浮点数通常是一个错误。在我编写的 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 和其他特殊值是可能的，但不太可能，以防万一这很重要。

有帮助吗？

解决方案

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

  • 如果 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，通过传递性规则等于0.24

（ETC）

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

其他提示

我不认为你可以有一个散列码与您的比较方法一致，因为后者不是传递性：对于任何三个矢量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）但是，散列码的平等总是传递的，因为它们只是数字。

在这种情况下，我只希望创建一个计算基础上上浮点坐标的精确值的哈希散列码方法，以及它与equals不一致的文件中提及。我知道这是不是一个真正的解决方案，但因为我不认为真正的解决办法存在，最好是有一个平凡的哈希码不仅仅是0。

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

取的任何两个数值a和b。让他们之间的区别是d。然后，如果你在它们之间的ε步骤创建d /小量数目，每一步必须是“等于”到步骤之前，其通过哈希码语义具有相同的散列码。因此，所有的数字必须具有相同的哈希码。

如果你添加一些其他的约束只能解决这个问题。

顺便说一句，你的Equals的定义是错误的，以及，因为它可以是真实的，a.Equals（b）和b.Equals（C），但不a.Equals（c）中，这是错误的平等。这被称为断裂的及物属性。

我能做些什么呢？

在解决方案取决于你使用的为乱码。一个解决方案是引入一个概念上的网格。更改equals和hashCode所以两个数字如果同一个网格立方体相等，按四舍五入到恒定的小数位数，然后取equals和hashCode的圆角数。如果是接近零是重要的情况下，添加一个偏置/ 2小量的舍入之前，所以零是立方体的中心。这是正确的，但你可以有两个号码任意并拢（下浮动的限制）不相等。因此，对于一些应用这将是确定，别人也不会。这类似于从一个想法 mghie 。

大家是正确...

但是，有一点是经常做是延长散列的概念的位。考虑您的3D空间的与箱的分隔用侧>>小量。

的点的哈希是它属于框。 当你想查找一个点，你不检查是否与相应的框中点（因为你会为一个普通的散列做），但邻近的盒子为好。在3D中，你应该摆脱最多8盒。

无论技术，你使用会出现问题，因为你带来的东西是不可能解决的。

你想要的是1）均匀分布散等

这对于大多数数字a和b，其中一个！= B，则a.GetHashCode（）！= b.GetHashCode（），但2）其中一个== B，则a.GetHashCode （）== b.GetHashCode（）必须是真实的。

返回一个常数满足（2），但不（1）。

可以证实，在1E-5的边界舍入，并将它作为散列违反满足（1），但违反（2）。以1E-5和2E-5，例如。四舍五入会产生两个不同的散列值，但他们比较相等。这违反了上述约束（2）。你可以很容易地推广这个证明号码的任何舍入将遇到类似的问题。

我建议你选择了不同的方法。我认为根本问题是确定一些点接近你已经有一个点。我建议recusively将坐标空间中的一半（其中沿边界点（即<= 1E-5在两半从边界））。如果逐步分割你的空间（认为二叉树），您可以构建一个数据结构，将很快返回你想要的结果，是相当容易的构建。

如果我错过了我的猜测，您必须使用哈希然后可以做你想做的两个哈希值每四舍五入到1E-5，但抵消5E-6是什么。所有相同的分数会比较平等的两个哈希值之一。这将要求您为每个哈希常规输入在哈希表点两次，一次。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top