Java HashMap put（）实现。为什么不先检查参考文献？

java standard-library

2022-09-04 23:25:26

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

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

即类似这样的东西：

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
}

这难道不会节省一个比较吗？

答案 1

我不知道为什么，但一个幼稚的微模板表明，在Oracle的VM（Intel，32或64位）上，比较两个引用大约需要比较两个int（如哈希代码）的四倍。我本来以为比较两个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;
}

答案 2

if_icmpne（整数比较）和if_acmpne（参考比较）的运算使用相同的技术来获得结果[1，2，3，4]。

两者都在堆栈上准备好了值，并平等地从堆栈中消耗。所需操作不应有显著差异。两者都将在单个 CPU 周期内完成。

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

它们的哈希码必须相等
当 x.equals（y）时必须返回 true

恕我直言，代码反映了这些规则，我可以写成

if (e.hash == hash && key.equals(k))

为了满足映射要求，我们必须始终验证哈希和等值。

因此，出于性能原因，该部件通过给予进行了优化key.equals(k)(k = e.key) == key

((k = e.key) == key || key.equals(k))

这种实现意味着对于映射，我们评估更多的哈希和等于，然后引用相等。所以这是预期的行为。

Java HashMap put（） 实现。为什么不先检查参考文献？

Java HashMap put（）实现。为什么不先检查参考文献？