java - Java HashMap 中双倍作为键的问题

Question

我遇到一个面试问题，我不确定正确答案是什么。

问题如下。

给定一个整数数组，返回两个数字的索引，使它们相加达到特定目标。

我解决这个问题的方法是循环遍历元素并将目标和元素之间的差异存储为映射中当前元素的键和索引。

然后，当差异出现在数组中时，我可以在 map 中查找哪个元素具有此差异以及 map 中的哪个索引。

到目前为止一切都很好。

但是，对于后续问题，“如果元素是双的怎么办”

我不确定问题是什么。

在搜索时，我遇到了几篇文章，提到了使用逻辑移位和使用 or 来计算哈希码的正确方法。但是，我看到 Java 的 Double.hashcode 函数中使用了类似的逻辑。

我认为问题可能是在计算 diff 时，可能会出现精度损失。因此，它最终可能会映射到不同的哈希桶。

但是，当我尝试时，我无法想出这样的输入。实际问题是什么？我该如何测试/解决它？

Java

我尝试简单地将数字更改为双倍，但逻辑运行良好。

Answer 1

这个程序用一个二元素数组说明了这个问题:

public strictfp class Test {
  public static void main(String[] args) {
    double in[] = {1e10, Math.nextUp(1e10)};
    double target = 2e10;
    System.out.println(in[0]+in[1]);
    double diff = target-in[0];
    System.out.println(diff);
    System.out.println(in[1] == diff);
    System.out.println(in[0]+in[1] == target);
  }
}

输出:

2.0E10
1.0E10
false
true

问题在于您的逻辑假设只有一个值，当添加到数组的元素时，会给出目标总和。由于四舍五入的原因，对于 double 元素，可以有多个值给出相同的总和。

在我的示例中，数组的两个元素之和等于目标，但第二个元素不等于 in[0] 与目标之间的差。

我对浮点版本问题的解决方案的第一个想法如下:

Create an array of ordered pairs containing value and index.
Sort by value.
For each element x, do a binary search for an element y such that x.value + y.value is equal to the target.
If you find one, return [x.index, y.index]

这是 O(n log(n))，其中 int 版本是 O(n)。