在 Java 中使用 Map 计数的几种姿势

一个老生常谈的问题：在 Java 中，如何使用 Map 给对象计数，例如统计字符串出现的次数？

姿势一：containsKey()

1
2
3
4
5
6
7
Map<String, Integer> map = new HashMap<>();
for (String word : words) {
    if (map.containsKey(word))
        map.put(word, map.get(word) + 1);
    else
        map.put(word, 1);
}

或者：

1
2
int count = map.containsKey(word) ? map.get(word) : 0;
map.put(word, count + 1);

这是最容易想到的方法，然而这种方法至少有两个问题：

Integer 中的 value 声明为 final，无法修改，每次更新均会产生一个新的 Integer 对象
过于频繁且不必要的查表，具体来说，在 map 中不含有 word 的情况下会查两次表，分别是 containsKey()、put() 方法；在含有 word 的情况下会查三次表，分别为 containsKey()、get()、put() 方法

姿势二：get() / getOrDefault()

1
2
3
4
5
Integer count = map.get(word);
if (count == null)
    map.put(word, 1);
else
    map.put(word, count + 1);

Java 8 则可以用 getOrDefault()：

1
map.put(word, map.getOrDefault(word, 0) + 1);

Integer 对象问题仍存在
改善了查表问题，不管 map 中是否已经存在 word，都只查两次表

姿势三：AtomicInteger / 自定义可变 int 封装类

1
Map<String, AtomicInteger> map = new HashMap<>();

1
2
3
4
5
AtomicInteger count = map.get(word);
if (count == null)
    map.put(word, new AtomicInteger(1));
else
    count.incrementAndGet();

利用 AtomicInteger，可以避免产生不必要的 Integer 对象。

也可以自己封装一个 MutableInt：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class MutableInt {
    int value = 1;

    public void increment() {
        ++value;
    }

    public int get() {
        return value;
    }
}

AtomicInteger 是为线程安全设计的，可能有一定性能损失，但我实际测试发现，AtomicInteger 与自己封装类的性能表现几乎相同。

解决了 Integer 对象问题
改善了查表问题，每次只查两次表

姿势四：利用 put() 方法的返回值

Map 的 put() 方法返回的是之前对应键的值，如果不存在，则为 null。

利用这一点就可以只查表一次即完成自增了：

1
2
3
4
AtomicInteger count = new AtomicInteger(1);
AtomicInteger old = map.put(word, count);
if (old != null)
    count.set(old.get() + 1);

每次仍产生一个冗余的 int 封装对象
只查表一次，大大提高效率

姿势五：Java 8 中的 merge() / compute()

1
map.merge(word, 1, (a, b) -> a + b);

或者：

1
map.merge(word, 1, Integer::sum);

也可以用 compute() 方法实现：

1
map.compute(word, (k, v) -> v == null ? 1 : v + 1);

虽然 Integer 对象问题仍存在，但只查一次表就实现了自增，Integer 自动拆箱装箱机制使代码非常简洁，如果使用 Java 8，毫无疑问代替姿势四。

当然 Integer 问题也是可以解决的，例如我们使用 AtomicInteger：

1
2
3
4
5
6
7
8
map.compute(word, (k, v) -> {
    if (v == null)
        return new AtomicInteger(1);
    else {
        v.incrementAndGet();
        return v;
    }
});

只不过代码没那么简洁了，这样既解决了 Integer 对象问题，又减少了查表时间。

总结

以下是我个人测试得到的性能表现：

在字符串重复率较高的情况下，姿势三 > 姿势五 > 姿势二 > 姿势四 > 姿势一

在重复率较低的情况下，姿势五 > 姿势二 > 姿势四 > 姿势一 > 姿势三

基本符合预期。

姿势一表现一直都较差
姿势二中规中矩，很多人也确实就是这样写的
姿势三避免了创建冗余对象，在重复率较高的情况下表现非常好，甚至好于姿势五
姿势四则比较奇葩，看似做了优化，但产生的冗余对象拖了后腿，代码可读性也不如其它，不建议使用
姿势五不管重复率如何整体表现都很稳定，代码也很简洁，如果不是量很大，那么使用封装类相比 Integer 优势不明显

以上均不考虑线程安全。