Java HashMap put() 实现。为什么不先检查引用？

Question

java.util.HashMap 实现了 put 方法，该方法内部包含 以下代码：

if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
}

在上面的代码中，为什么没有首先进行引用检查（因为具有相同引用的两个对象将具有相同的哈希和相等性）？

例如这样：

if ((k = e.key) == key) {
    V oldValue = e.value;
    e.value = value;
    e.recordAccess(this);
    return oldValue;
} else if ( compare hash and equals) {
    // do something again with the value
}

这样不是可以省去一次比较吗？

- Ace McCloud

---

有些情况下，这将省去一次比较。 - Denys Séguret

是的，我同意，在某些情况下只进行比较可以节省时间。 - Ace McCloud

建议您向Oracle提出修复建议，他们可能会将其应用于Java 9。 - AlexR

如果你的建议平均速度更快，那么它才是有益的。那么，平均而言，它是否更快呢？ - user207421

如果 (k = e.key) == key) { 应该改为 if ((k = e.key) == key) { - avgvstvs

Answer 1

我不知道为什么，但是一个天真的微基准测试表明，在Oracle的虚拟机上（Intel，32位或64位），比较两个引用需要的时间大约是比较两个整数（如哈希码）需要的时间的四倍。我原以为在现代硬件上，比较两个32位整数和两个地址指针应该具有类似的运行时成本，但我可能没有考虑到一些显而易见的东西。

假设大多数情况下不同键具有不同的哈希码，在比较关键字之前先比较哈希码可以为每个不正确的键保存75%的运行时间，并为正确的键增加25%的运行时间。当然，这是否实际节省了总体运行时间取决于哈希表格的确切内容和布局，但Sun工程师显然认为这种变体对于大多数目的更好。

用于基准测试的方法：

public static int c1(int a, int b, int iter) {
    int r = 0;
    while((iter--)>0) {
        if(a == b) {
            r++;
        }
    }
    return r;
}

public static int c2(Object a, Object b, int iter) {
    int r = 0;
    while((iter--)>0) {
        if(a == b) {
            r++;
        }
    }
    return r;
}

- jarnbjo

---

请展示一下基准测试。看你的声望，应该能够编写有效的基准测试，但为了确保，你知道的 :) - Martijn Courteaux

@MartijnCourteaux：好的。 - jarnbjo

请展示更多的代码。我认为这段代码在自动优化方面已经非常可疑了。基准测试对你忘记做的各种小事情非常敏感。例如：错误使用这些方法可能会导致你的方法根本不执行任何操作。我的意思是，真的什么都不做。编译器可能会直接优化掉整个方法调用。我不确定JIT是否会在通过阈值后优化掉比较。有人能确认一下吗？ - Martijn Courteaux

@Martijn：当然，优化器有可能在某个时刻决定条件（a == b）永远不会改变，但只要c1和c2之间的运行时比率保持相对恒定，独立于迭代次数，我至少会首先假设差异是由于比较整数而不是引用所导致的。 - jarnbjo

Answer 2

操作if_icmpne（整数比较）和if_acmpne（引用比较）使用相同的技术来获取结果[1, 2, 3, 4]。

两者在堆栈上准备值，并且从中消耗的方式相同。所需的操作应该没有显着差异。两者都将在单个CPU周期内完成。

为了表明 map 可以将对象存储在同一个 bucket 中，必须验证两个规则。

• 它们的哈希码必须相等
• x.equals(y) 必须返回 true

我认为代码反映了这些规则，并且可以写成： if (e.hash == hash && key.equals(k)) 为了满足 map 的要求，我们必须始终验证哈希和 equals。

出于性能原因，部分 key.equals(k) 通过优化 (k = e.key) == key 进行了优化，得到： ((k = e.key) == key || key.equals(k)) 这种实现意味着对于 maps，我们比引用相等性更加重视哈希和 equals。因此，这是预期的行为。

- Damian Leszczyński - Vash