具有公差级别的双精度哈希方法

Question

我实现了一个 equals 方法，如下所示，具有双精度容忍度。

public boolean equals(Object obj) {
    // Checking for not null and same class etc.
    return approxEqual(this,other);
}

private static boolean approxEqual(final Position p1, final Position p2) {
    double distance = // distance function between positions
    return Double.compare(distance, TOLERANCE) <= 0;
}

因为我正在使用 HashSets，所以我需要一个具有相同功能的散列方法。你们知道怎么做吗？

我知道，容忍度不是很好，因为 equals 方法应该是可传递的。但是我需要平衡测量的不准确性。

Answer 1

不幸的是，我认为这违背了哈希的本质。

A k-d-tree 或二进制搜索是作为替代解决方案首先想到的。

Answer 2

假设：假设您现在的公差为 1。这意味着 0 等于 0.8，因为它们的差异低于公差。然后让我们比较 0.8 和 1.5，它们相等，因为它们的差异是 0.7 < 1。这意味着它们将获得相同的哈希值，这意味着 0 和 1.5 具有相同的哈希值，重复该过程和一切会得到相同的散列值/相等。

这没有道理，是吗？你不能做 equal 或 hashcode 宽容。

Answer 3

使用 TreeMap 而不是 HashMap。

如果您在 compareTo / compare 方法中实施容差，那么任何键查找/插入都将 "snap" 到容差范围内的现有键。

当然还有一个警告，即插入顺序可能会影响结果。例如。如果 tolerance 为 5，并且您有值 2、6 和 9，则首先添加 6 会将 2 和 9 都捕捉到 6 值，结果是一个键 (6)，否则您最终会得到两个键 ( 2 和 9) 并且 6 捕捉到 2 还是 9 是任意的。

有了宽容，对于这种不可预测性你真的无能为力，所以我相信这是解决你问题的最佳方法。

Answer 4

您可以将您的数据分成多个范围，然后说某个范围内的所有内容都是相等的。
您可以通过四舍五入来做到这一点（确切的细节取决于您要寻找的公差级别，对于下面的内容，您可以简单地使用 floor）。

因此，如果我们拆分为 1 的范围，我们可以说 0 和 1 之间的所有内容（不包括 1，即 [0,1) 范围内的内容）都相等，并且 1 和 2 之间的所有内容都相等,等等。

然而，这确实会产生一个问题，即 彼此非常接近的元素可能不相等 如果它们在不同的范围内，例如，对于上述情况，0.9999 不会被认为等于 1.0001.

如果您尝试仅为此使用相等性（和散列），则此问题并非完全可以避免，因为扩展这些范围并不能解决此问题，并且试图使它们重叠会产生新问题。

根据您尝试使用它的方式，可能可以通过多次查找来解决上述问题，因此您在 [0,1] 范围和 [1, 2]范围。如果您说尝试进行查找以查找在某个其他元素的一定公差范围内的所有元素（这与将元素视为相等并不完全相同），这将起作用。

如果这对您不起作用，哈希可能不是您正在寻找的解决方案，您可能想要考虑一个有序的数据集，例如TreeMap（或者确实是 kd 树，如另一个答案中所述）。

这主要基于 1D 数据（即双精度），但可以通过四舍五入每个维度轻松扩展到 2D（方形范围）或 3D（立方体范围）。如果您如上所述进行多次查找，则可能不需要进行 1 次查找（最接近的范围），而是在 2D 中最多进行 3 次查找（水平和垂直方向上最接近的方形范围，以及与这两个范围相邻的方形），对于 3D 也是如此。

具有公差级别的双精度哈希方法

Hash Method for doubles with tolerance level

java

hash

equals