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

Question

map 的一个常见模式是检查键是否存在，然后仅在存在时才对值进行操作，请考虑:

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

然而，这通常被认为很差，因为它需要两次 map 查找，而这种替代方法只需要一次:

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

然而，这第二个实现有它自己的问题。除了不够简洁和可读之外，它还可能不正确，因为它无法区分 key 不存在和 key 存在但显式映射到 null 的情况。当然，在个别情况下，我们可以创建 map 不包含 null 值的外部不变量，但通常我们不能依赖第二种模式，需要回退到效率较低的实现。

但为什么第一次实现需要效率较低？ HashMap 的 .containsKey() 看起来像这样:

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

和Guava的ImmutableMap.containsKey()类似的是:

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

由于这些调用完成了执行 .get() 的所有工作，缓存此调用的结果然后短路对 的连续调用的缺点是什么.get() 获取相同的 key ？成本似乎是一个单一的指针，但好处意味着实现这种模式的“正确”方式也是“有效”的方式。

---

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

因为缓存假设了一个特定的用例，但实际上会减慢其他用例的速度。它还增加了很多并发症。

如何缓存值？当多个线程同时读取时会发生什么？

坐下来开始思考这里可能发生的各种边缘情况和问题。例如，如果值在 contains 调用和 get 调用之间发生更改。这样一个看似简单的更改实际上引入了很多复杂性并减慢了很多实际上比这个特定序列更可能被更频繁使用的操作。

您还应该考虑在非缓存 map 之上构建“缓存 map ”是可能的，但相反的情况是不可能的。