为什么常见的Map实现不会为Map.get()缓存Map.containsKey()的结果

Question

带有映射的常见模式是检查密钥是否存在,然后仅在其执行时对该值执行操作,请考虑:

if(!map.containsKey(key)) {
  map.put(key, new DefaultValue());
}
return map.get(key);

然而,这通常被认为很差,因为它需要两个地图查找,其中此替代方案仅需要一个:

Value result = map.get(key);
if(result == null) 
{
  result = new DefaultValue();
  map.put(key,result);
}
return result;

然而,第二个实现有它自己的问题.除了不那么简洁和可读之外,它可能是不正确的,因为它无法区分密钥不存在的情况和密钥存在的位置但是明确映射到的情况null.在个别情况下,我们当然可以创建外部不变量,地图不会包含null值,但一般来说,我们不能依赖第二种模式,需要回退到效率较低的实现.

但为什么第一次实施需要效率较低？ HashMap的.containsKey()是这样的:

public boolean containsKey(Object key) {
  return getEntry(key) != null;
}

和番石榴ImmutableMap.containsKey()类似的是:

public boolean containsKey(@Nullable Object key) {
  return get(key) != null;
}

由于这些调用都是通过执行a的所有工作,.get()缓存此调用的结果有什么不利之处,然后将连续调用短路连接到.get()同一个键？看起来成本是一个单指针,但好处意味着实现这种模式的"正确"方式也是"有效"的方式.

---

private transient Entry<K,V> lastContainsKeyResult = null;

public boolean containsKey(Object key) {
  lastContainsKeyResult = getEntry(key);
  return lastContainsKeyResult != null;
}

public V get(Object key) {
  if(key != null && lastContainsKeyResult != null && 
     key.equals(lastContainsKeyResult.getKey()) {
    return lastContainsKeyResult.getValue();
  }
  // normal hash lookup
}

Answer 1

因为缓存假设一个特定的用例,但实际上会减慢其他用户的速度.它还增加了很多复杂性.

你如何缓存价值？当多个线程一次读取时会发生什么？

坐下来开始思考所有可能发生的各种边缘情况和问题.例如,如果在包含调用和get调用之间更改了值.这样一个看似简单的变化实际上是引入了大量的复杂性并减慢了很多这实际上更可能是使用频率高于这个特定的操作顺序.

您还应该考虑在非缓存之上构建"缓存映射",但相反的情况是不可能的.