代码之家 › 专栏 › 技术社区 › synthax

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

equals hash java

synthax · 技术社区 · 7 年前

我实现了一个equals方法,如下所示,并为double设置了一个容差级别。

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;
}

正如我所用 HashSet 我需要一个具有相同功能的哈希方法。你们知道怎么做吗?

我知道,容忍度并不是很好,因为equals方法应该是可传递的。但我需要平衡测量误差。

4 回复 | 直到 7 年前

luk2302 7 年前

假设的 :假设您的容差目前为1。这意味着0等于0.8,因为它们的差值小于公差。然后比较0.8和1.5,它们相等,因为它们的差值为0.7<1、这意味着它们将获得相同的哈希值,这意味着0和1.5具有相同的哈希值,重复该过程 每件事 将获得相同的哈希值/相等。

这没有道理,是吗?你不能这样做 equal 或 hashcode 具有公差。

DHa 7 年前

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

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

Andreas dfa 7 年前

使用 TreeMap 而不是 HashMap .

如果在 compareTo / compare 方法,则任何键查找/插入都将“捕捉”到公差范围内的现有键。

当然,还有一个警告,即插入顺序可能会影响结果。E、 g.如果公差为5,并且您有值2、6和9,那么首先添加6会将2和9捕捉到6值,结果是一个键(6),否则您将得到两个键(2和9),并且6捕捉到2还是9是任意的。

有了宽容,你真的无法应对这种不可预测性,所以我相信这是解决你问题的最好办法。

Bernhard Barker 7 年前

你可以 将数据拆分为多个范围 并且说在某个范围内的一切都是平等的。
您可以通过舍入来实现这一点(确切的细节取决于您所寻找的公差级别,对于以下内容,您可以简单地使用 floor ).

因此,如果我们分裂成1的范围,我们可以说0和1之间的一切(不包括1,即在范围[0,1]内)都是相等的,1和2之间的一切都是相等的,依此类推。

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

如果您试图对此仅使用相等(和哈希),那么这个问题是无法完全避免的,因为扩展这些范围并不能解决这个问题,而试图使它们重叠会产生新的问题。

根据您尝试如何使用它,可能通过多次查找来解决上述问题,因此您可以在[0,1]范围和[1,2]范围内都考虑0.9999。如果您尝试进行查找,以找到与其他元素在一定公差范围内的所有元素(这与将元素视为相等并不完全相同),那么这将起作用。

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

这主要基于1D数据(即双倍数据),但通过对每个维度进行舍入,可以很容易地将其扩展到2D(正方形范围)或3D(立方体范围)。如果如上所述进行多个查找,则可能不需要进行1次查找(最接近的范围),而需要在2D中进行最多3次查找(水平和垂直方向上最接近的正方形范围,以及与这两者相邻的正方形),对于3D也是如此。