在 Java 中递增 Map 值的最有效方法

Question

我希望这个问题对于这个论坛来说不会被认为太基础，但我们会看到。我想知道如何重构一些代码以获得运行多次的更好性能。

假设我正在使用 Map（可能是 HashMap）创建一个词频列表，其中每个键都是一个字符串，其中包含要计算的单词，值是一个整数，每次找到单词的标记时都会递增。

在 Perl 中，递增这样的值非常容易：

 $map{$word}++;

但在 Java 中，它要复杂得多。这是我目前正在做的方式：

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

这当然依赖于较新 Java 版本中的自动装箱功能。我想知道您是否可以建议一种更有效的方法来增加这种价值。是否有更好的性能理由来避开 Collections 框架并使用其他东西来代替？

更新：我已经对几个答案进行了测试。见下文。

原文由 gregory 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

部分测试结果

对于这个问题，我已经得到了很多很好的答案——谢谢大家——所以我决定进行一些测试，找出哪种方法实际上最快。我测试的五种方法是：

• 我在 问题 中提出的“ContainsKey”方法
• Aleksandar Dimitrov 建议的“TestForNull”方法
• Hank Gay 建议的“AtomicLong”方法
• jrudolph 建议的“Trove”方法
• phax.myopenid.com 建议的“MutableInt”方法

方法

这就是我所做的……

1. 创建了五个相同的类，除了如下所示的差异。每个班级都必须执行我介绍的场景中的典型操作：打开一个 10MB 的文件并将其读入，然后对文件中的所有单词标记执行频率计数。由于这平均只用了 3 秒，我让它执行了 10 次频率计数（不是 I/O）。
2. 对 10 次迭代的循环进行计时，但 不对 I/O 操作 进行计时，并基本上使用 Java Cookbook 中的 Ian Darwin 方法 记录所用的总时间（以时钟秒为单位）。
3. 依次执行所有五项测试，然后再执行三次。
4. 对每种方法的四个结果进行平均。

结果

我将首先展示结果，然后为感兴趣的人展示下面的代码。

正如预期的那样， ContainsKey 方法是最慢的，因此我将给出每个方法的速度与该方法的速度的比较。

• ContainsKey： 30.654 秒（基线）
• AtomicLong： 29.780 秒（快 1.03 倍）
• TestForNull： 28.804 秒（快 1.06 倍）
• Trove： 26.313 秒（快 1.16 倍）
• MutableInt： 25.747 秒（快 1.19 倍）

结论

似乎只有 MutableInt 方法和 Trove 方法明显更快，因为只有它们提供了超过 10% 的性能提升。但是，如果线程是一个问题，AtomicLong 可能比其他的更有吸引力（我不太确定）。我还使用 final 变量运行了 TestForNull，但差异可以忽略不计。

请注意，我没有分析不同场景中的内存使用情况。我很高兴听到任何人对 MutableInt 和 Trove 方法可能会如何影响内存使用有很好的见解。

就个人而言，我发现 MutableInt 方法最有吸引力，因为它不需要加载任何第三方类。所以除非我发现它有问题，否则这是我最有可能走的路。

编码

这是每个方法的关键代码。

包含密钥

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
int count = freq.containsKey(word) ? freq.get(word) : 0;
freq.put(word, count + 1);

测试为空

import java.util.HashMap;
import java.util.Map;
...
Map<String, Integer> freq = new HashMap<String, Integer>();
...
Integer count = freq.get(word);
if (count == null) {
    freq.put(word, 1);
}
else {
    freq.put(word, count + 1);
}

原子长

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.atomic.AtomicLong;
...
final ConcurrentMap<String, AtomicLong> map =
    new ConcurrentHashMap<String, AtomicLong>();
...
map.putIfAbsent(word, new AtomicLong(0));
map.get(word).incrementAndGet();

宝库

import gnu.trove.TObjectIntHashMap;
...
TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
...
freq.adjustOrPutValue(word, 1, 1);

可变整数

import java.util.HashMap;
import java.util.Map;
...
class MutableInt {
  int value = 1; // note that we start at 1 since we're counting
  public void increment () { ++value;      }
  public int  get ()       { return value; }
}
...
Map<String, MutableInt> freq = new HashMap<String, MutableInt>();
...
MutableInt count = freq.get(word);
if (count == null) {
    freq.put(word, new MutableInt());
}
else {
    count.increment();
}

原文由 gregory 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

现在，使用 Map::merge 的 Java 8 有更短的方法。

 myMap.merge(key, 1, Integer::sum)

它能做什么：

• 如果 键 不存在，将 1 作为值
• 否则将 1 加到链接到 键 的值

更多信息 在这里。

原文由 LE GALL Benoît 发布，翻译遵循 CC BY-SA 4.0 许可协议