Java浮点数的哈希码

Question

我想要在一个哈希映射中使用 Double （或者 Float）类型作为键。

Map<Double, String> map = new HashMap<Double, String>()
map.put(1.0, "one");
System.out.println(map.containsKey(Math.tan(Math.PI / 4)));

这将返回false。

如果我要比较这两个数字，我会这样做：

final double EPSILON = 1e-6;
Math.abs(1.0 - Math.tan(Math.PI / 4)) < EPSILON

但是由于Hashmap使用了hashcode，这对我造成了一些困扰。

我考虑实现一个roundKey函数，在将其用作键之前，将其舍入为EPSILON的某个倍数。

map.put(roundKey(1.0), "one")
map.containsKey(roundKey(Math.tan(Math.PI / 4)))

• 有没有更好的方法？
• 如何正确实现这个roundKey?

- mzzzzb

---

可能是HashMap中的Double重复问题。 - Joe

实现一个好的roundKey函数可能会很麻烦，因为你需要避免出现"1.00000000001"和"0.999999999999"这样的问题：在舍入浮点数时你得到了一个浮点数。也许你想要实现一个floatToKey函数，它返回int类型？ - Dmitry Bychenko

Answer 1

如果你知道适当的舍入方式，可以使用它。例如，如果需要舍入到美分，可以将其舍入到两个小数位。

然而，对于上面的例子，固定精度的离散舍入可能不合适。例如，如果将其舍入到6个小数位，1.4999e-6和1.5001e-6将无法匹配，因为其中一个向上舍入，另一个向下舍入，尽管差异小于1e-6。

在这种情况下，最接近的方法是使用NavigableMap。

NavigableMap<Double, String> map = new TreeMap<>();

double x = ....;
double error = 1e-6;

NavigableMap<Double, String> map2 = map.subMap(x - error, x + error);

或者您可以使用

Map.Entry<Double, String> higher = map.higherEntry(x);
Map.Entry<Double, String> lower = map.lowerEntry(x);
Map.Entry<Double, String> entry = null;
if (higher == null)
    entry = lower;
else if (lower == null)
    entry = higher;
else if (Math.abs(lower.getKey() - x) < Math.abs(higher.getkey() - x))
    entry = lower;
else
    entry = higher;
// entry is the closest match.
if (entry != null && Math.abs(entry - x) < error) {
    // found the closest entry within the error
}

这将查找连续范围内的所有条目。

- Peter Lawrey

---

@mzzzzb 注意：NavigableMap可以在范围内找到多个键，但如果为空，则没有找到。 - Peter Lawrey

Answer 2

最好的方法是不要使用浮点数作为键，因为它们（正如您发现的那样）无法进行比较。
像在一定范围内调用它们相同这样的笨拙“解决方案”只会导致以后出现问题，因为您要么必须扩展过滤器，要么必须在时间上更加严格，两者都可能导致现有代码存在潜在问题，或者人们会忘记事物应该如何工作。
当然，在某些应用程序中，您希望这样做，但作为查找某些东西的关键吗？不。您可能最好使用角度和整数作为这里的键。如果需要比1度更高的精度，请使用角度，例如十分之一度通过存储0到3600的数字。
这将为您提供可靠的Map行为，同时保留您计划存储的数据。

- jwenting

---

关键问题在于有一个值几乎但不完全相同，你仍然希望它匹配。使用整数也不会改变这一点。如果你有0到3600，但想让1234与1235匹配，问题是一样的。 - Peter Lawrey

@PeterLawrey 确实如此，但这是假设您通常想要的键的反向。 - jwenting

@jwenting Peter的观点是，如果这些整数是浮点计算的结果，那么存储整数键并不能解决问题。无论是在存储和查找时计算完全相同的浮点值（在这种情况下存储浮点键会起作用），还是没有（在这种情况下整数只是一种笨拙和不完美的解决方案）。44.4999999999和44.50000000001一旦舍入到整数，它们将以不同的方式进行散列，尽管它们在彼此的浮点误差范围内。 - Sneftel