TestForNull的地图查找效率

Question

Referencing a previous answer to a question on SO, 有一个方法叫做TestForNull。这是我被告知可以提高效率之前的原始代码：

我的原码：

for (int i = 0; i < temp.length; i++) {
            if (map.containsKey(temp[i]))
                map.put(temp[i], map.get(temp[i]) + 1);
            else
                map.put(temp[i], 1);

在此代码段中，我对地图进行了三次查找。有人告诉我这可以在一次查找中完成，所以我最终在 SO 上寻找答案并找到了链接的答案，并将我的代码修改为如下所示：

我修改的代码：

for (int i = 0; i < temp.length; i++) {
            Integer value = map.get(temp[i]); 
            if (value != null)
                map.put(temp[i], value + 1);
            else
                map.put(temp[i], 1);
        }

尽管看起来更好，但对我来说它看起来像是两次查找而不是一次。我想知道是否有一个只使用一个的实现，是否可以在不使用第三方库的情况下完成。如果有帮助，我正在为我的程序使用 HashMap。

Answer 1

Java 8 向 Map 接口添加了一些 default 方法，包括 merge:

map.merge(temp[i], 1, v -> v + 1);

和compute：

map.compute(temp[i], (k, v) -> v == null ? 1 : v + 1);

HashMap's implementations of these methods 被适当优化以有效地仅执行单个键查找。（奇怪的是，TreeMap 却不是这样。）

Answer 2

@John Kugelman 的回答是最好的（只要你能用java 8）。

第一个例子有 3 个 map 调用的最坏情况（在值已经存在的情况下）：

包含密钥
得到
放

第二个例子总是恰好有 2 次调用（和空检查）：

得到
放

所以您基本上是在用 containsKey 换取空值支票。

在 HashMap 中，这些操作大致是常数时间，假设散列码分布良好（并且该分布与 HashMap 的大小配合得很好）。其他 Map 实现（例如 TreeMap）的执行时间为 log(n)。即使在 HashMap 的情况下，空检查也会比 containsKey 更快，使第二个选项成为赢家。但是，您不太可能有可测量的差异，除非您的散列码分布不佳（或者这是您的应用程序正在做的唯一事情）或执行不佳的相等检查。

TestForNull的地图查找效率

Map Lookup Efficiency of TestForNull

java

lookup

performance

dictionary