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

我希望这个问题不被视为这个论坛的基础，但我们会看到。 我想知道如何重构一些代码，以获得更好的性能，这是一堆运行。

假设我正在创build一个词频列表，使用一个Map（可能是一个HashMap），其中每个键都是一个string，其中的单词是被计数的，并且该值是一个整数，每次find该单词的一个标记时，该整数就会递增。

在Perl中，增加这样一个值将是非常简单的：

$map{$word}++; 

但在Java中，它更复杂。 这里我正在做的方式是：

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

当然这依赖于较新的Java版本中的自动装箱function。 我想知道你是否可以提出一个更有效的方式来增加这样的价值。 是否有避免使用Collections框架和使用其他方法的良好性能？

更新：我已经做了几个答案的testing。 见下文。

Answer 1

一些testing结果

我已经得到了很多很好的答案 – 谢谢大家 – 所以我决定进行一些testing，找出哪种方法实际上是最快的。 我testing的五种方法是：

• 我在问题中提出的“ContainsKey”方法
• Aleksandar Dimitrovbuild议的“TestForNull”方法
• Hank Gay提出的“AtomicLong”方法
• jrudolphbuild议的“Trove”方法
• phax.myopenid.combuild议的“MutableInt”方法

方法

这是我做的…

1. 除了下面显示的差异之外，创build了五个相同的类。 每个class级都必须执行典型的操作：打开一个10MB的文件并读入，然后执行文件中所有单词标记的频率计数。 由于这平均只需要3秒，所以我执行了10次频率计数（而不是I / O）。
2. 对10次迭代的循环进行计时，但不对I / O操作进行计时，并基本上使用Java Cookbook中的Ian Darwin方法logging总时间（以时钟秒为单位）。
3. 连续进行了五个testing，然后又做了三次。
4. 平均每种方法的四个结果。

结果

我将首先介绍结果以及下面的代码。

正如所料， ContainsKey方法是最慢的，所以我会给每个方法的速度比较该方法的速度。

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

结论

看来只有MutableInt方法和Trove方法要快得多，因为只有10％以上的性能提升。 但是，如果线程是一个问题，AtomicLong可能比其他人更有吸引力（我不太确定）。 我也运行TestForNull与finalvariables，但差异是微不足道的。

请注意，我没有在不同情况下分析内存使用情况。 我很高兴听到任何人对MutableInt和Trove方法可能影响内存使用情况的深入了解。

就个人而言，我发现MutableInt方法最吸引人，因为它不需要加载任何第三方类。 所以除非我发现问题，那就是我最可能去的方式。

代码

这里是每种方法的关键代码。

的containsKey

 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); 

TestForNull

 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); } 

的AtomicLong

 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); 

MutableInt

 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(); } 

Answer 2

2016年的一点研究： https ： //github.com/leventov/java-word-count ， 基准源代码

每种方法的最佳结果（越小越好）：

  time, ms kolobokeCompile 18.8 koloboke 19.8 trove 20.8 fastutil 22.7 mutableInt 24.3 atomicInteger 25.3 eclipse 26.9 hashMap 28.0 hppc 33.6 hppcRt 36.5 

时间\空间结果：

Answer 3

@Hank Gay

作为我自己（相当无用）的评论的后续行动：Trove看起来像是要走的路。 如果出于任何原因，你想坚持使用标准的JDK， ConcurrentMap和AtomicLong可以使代码更好一点，虽然YMMV。

  final ConcurrentMap<String, AtomicLong> map = new ConcurrentHashMap<String, AtomicLong>(); map.putIfAbsent("foo", new AtomicLong(0)); map.get("foo").incrementAndGet(); 

会在foo的地图上留下1作为值。 实际上，增加线程的友好性是这种方法必须推荐的。

Answer 4

好吧，可能是一个老问题，但Java 8有一个较短的方法：

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

它的作用是：如果键不存在，则将1作为值，否则将1加到链接到键的值上。 更多信息在这里

Answer 5

在Google Collections Library中查看这种情况总是一个好主意。 在这种情况下， Multiset会诀窍：

 Multiset bag = Multisets.newHashMultiset(); String word = "foo"; bag.add(word); bag.add(word); System.out.println(bag.count(word)); // Prints 2 

有像迭代键/条目等类似地图的方法，在内部实现当前使用HashMap<E, AtomicInteger> ，所以你不会承担拳击费用。

Answer 6

谷歌番石榴是你的朋友…

至less在某些情况下 他们有这个漂亮的AtomicLongMap 。 特别好，因为你在地图上处理的价值很高。

例如

 AtomicLongMap map = AtomicLongMap.create(); [...] map.getAndIncrement(word); 

也可以添加更多的1的值：

 map.getAndAdd(word, new Long(112)); 

Answer 7

你应该知道你最初的尝试

  int count = map.containsKey（word）？  map.get（word）：0; 

在地图上包含两个潜在的昂贵操作，即containsKey和get 。 前者执行的操作可能与后者非常相似，所以你做了两次相同的工作！

如果您查看Map的API，则当映射不包含请求的元素时， get操作通常会返回null 。

请注意，这将使解决scheme

  map.put（key，map.get（key）+ 1）; 

危险的，因为它可能会产生NullPointerException s。 你应该首先检查null 。

还要注意 ，这非常重要， HashMap 可以按照定义包含nulls 。 所以不是每一个返回的null都说“没有这样的元素”。 在这方面， containsKey行为与实际告诉你是否存在这样一个元素有所不同 。 有关详细信息，请参阅API。

但是，对于您的情况，您可能不想区分存储的null和“noSuchElement”。 如果你不想允许null你可能更喜欢一个Hashtable 。 使用其他答案中已经提出的包装库可能是更好的手动处理解决scheme，具体取决于应用程序的复杂性。

为了完成答案（我忘了把它放在第一位，感谢编辑function！），最好的办法就是进入finalvariables，检查是否为null然后put它put回到1 。 variables应该是final因为它是不可改变的。 编译器可能不需要这个提示，但它更清晰。

 final HashMap map = generateRandomHashMap（）;
 final Object key = fetchSomeKey（）;
 final Integer i = map.get（key）;
 if（i！= null）{
     map.put（i + 1）;
 } else {
     // 做一点事
 }

如果你不想依靠自动装箱，你应该说像map.put(new Integer(1 + i.getValue())); 代替。

Answer 8

另一种方法是创build一个可变的整数：

 class MutableInt { int value = 0; public void inc () { ++value; } public int get () { return value; } } ... Map<String,MutableInt> map = new HashMap<String,MutableInt> (); MutableInt value = map.get (key); if (value == null) { value = new MutableInt (); map.put (key, value); } else { value.inc (); } 

当然这意味着创build一个额外的对象，但与创build一个Integer（即使与Integer.valueOf）相比，开销不应该太大。

Answer 9

 Map<String, Integer> map = new HashMap<>(); String key = "a random key"; int count = map.getOrDefault(key, 0); map.put(key, count + 1); 

这就是你如何用简单的代码增加一个值。

效益：

• 不为可变int创build另一个类
• 短代码
• 容易明白
• 没有空指针exception

另一种方法是使用合并方法，但这太多了，只是递增一个值。

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

build议：在大多数情况下，您应该关心代码可读性而不是性能提升。

Answer 10

内存旋转可能是一个问题，因为每个大于或等于128的int的装箱都会导致对象分配（请参阅Integer.valueOf（int））。 尽pipe垃圾收集器非常有效地处理短暂的对象，但是性能会受到一定程度的影响。

如果你知道所做增量的数量将远远超过键的数量（在这种情况下=字），请考虑使用一个int持有者。 Phax已经为此提供了代码。 这里又有两个变化（持有者类别为static，初始值设为1）：

 static class MutableInt { int value = 1; void inc() { ++value; } int get() { return value; } } ... Map<String,MutableInt> map = new HashMap<String,MutableInt>(); MutableInt value = map.get(key); if (value == null) { value = new MutableInt(); map.put(key, value); } else { value.inc(); } 

如果您需要极高的性能，请查找直接针对原始值types定制的Map实现。 jrudolph提到了GNU Trove 。

顺便说一下，这个主题的好search词是“直方图”。

Answer 11

而不是调用containsKey（），只需要调用map.get，并检查返回的值是否为null即可。

  Integer count = map.get(word); if(count == null){ count = 0; } map.put(word, count + 1); 

Answer 12

你确定这是一个瓶颈吗？ 你有没有做过任何性能分析？

尝试使用NetBeans Profiler（免费并内置到NB 6.1）来查看热点。

最后，JVM升级（比如从1.5-> 1.6）通常是一个便宜的性能增强器。 即使内部版本号升级也可以提供很好的性能提升。 如果您在Windows上运行并且这是服务器类应用程序，请在命令行上使用-server来使用服务器热点JVM。 在Linux和Solaris机器上，这是自动检测的。

Answer 13

有几种方法：

1. 使用与Googlecollections集中包含的套件一样的套件。

2. 创build可在Map中使用的可变容器：

class My{ String word; int count; }
class My{ String word; int count; } 

并用put（“word”，new我的（“word”））; 然后你可以检查是否存在，增加时增加。

避免使用列表滚动你自己的解决scheme，因为如果你得到innerloopsearch和sorting，你的performance会很糟糕。 第一个HashMap解决scheme实际上是相当快的，但在Google Collections中find的恰当的方式可能会更好。

用Google Collections计算单词，看起来像这样：

HashMultiset s = new HashMultiset(); s.add("word"); s.add("word"); System.out.println(""+s.count("word") );
HashMultiset s = new HashMultiset(); s.add("word"); s.add("word"); System.out.println(""+s.count("word") ); 

使用HashMultiset是非常优雅的，因为一个bag-algorithm就是你计算单词时所需要的。

Answer 14

我认为你的解决scheme将是标准的方式，但是 – 正如你自己所指出的 – 这可能不是最快的方法。

你可以看看GNU Trove 。 这是一个包含各种快速原始集合的库。 你的例子将使用TObjectIntHashMap，它有一个方法adjustOrPutValue，它正是你想要的。

Answer 15

MutableInt方法的一个变种可能会更快一些，如果有点诡计，就是使用单元素的int数组：

 Map<String,int[]> map = new HashMap<String,int[]>(); ... int[] value = map.get(key); if (value == null) map.put(key, new int[]{1} ); else ++value[0]; 

如果你可以重新运行你的性能testing这个变化，这将是有趣的。 这可能是最快的。

---

编辑：上面的模式对我来说工作得很好，但最终我改变了使用Trove的集合，以减less我创build的一些非常大的地图的内存大小 – 作为奖励它也更快。

一个非常好的特性是adjustOrPutValue类有一个adjustOrPutValue调用，根据在这个键上是否有一个值，将调用一个初始值或者递增现有的值。 这对增量是完美的：

 TObjectIntHashMap<String> map = new TObjectIntHashMap<String>(); ... map.adjustOrPutValue(key, 1, 1); 

Answer 16

Google Collections HashMultiset：
– 使用相当优雅
– 但消耗CPU和内存

最好的办法是像这样： Entry<K,V> getOrPut(K); （优雅，低成本）

这样的方法只会计算一次哈希和索引，然后我们可以用条目来做我们想要的（replace或更新值）。

更优雅：
– 取一个HashSet<Entry>
– 扩展它，以便get(K)如果需要的话放入一个新的条目
– 进入可能是你自己的对象。
– > (new MyHashSet()).get(k).increment();

Answer 17

“放”需要“拿”（确保没有重复的键）。
所以直接做一个“放”
如果有以前的价值，那么做一个补充：

 Map map = new HashMap (); MutableInt newValue = new MutableInt (1); // default = inc MutableInt oldValue = map.put (key, newValue); if (oldValue != null) { newValue.add(oldValue); // old + inc } 

如果计数从0开始，则加1 :(或其他值…）

 Map map = new HashMap (); MutableInt newValue = new MutableInt (0); // default MutableInt oldValue = map.put (key, newValue); if (oldValue != null) { newValue.setValue(oldValue + 1); // old + inc } 

注意：这段代码不是线程安全的。 用它来build立然后使用地图，而不是同时更新它。

优化：在一个循环中，保持旧的值成为下一个循环的新值。

 Map map = new HashMap (); final int defaut = 0; final int inc = 1; MutableInt oldValue = new MutableInt (default); while(true) { MutableInt newValue = oldValue; oldValue = map.put (key, newValue); // insert or... if (oldValue != null) { newValue.setValue(oldValue + inc); // ...update oldValue.setValue(default); // reuse } else oldValue = new MutableInt (default); // renew } } 

Answer 18

各种各样的原始包装，例如Integer是不可变的，所以除非你能用AtomicLong这样的东西来做， 否则真的没有更简洁的方法去做你正在问的东西。 我可以在一分钟内给出一个更新。 顺便说一下， Hashtable 是 集合框架的一部分。

Answer 19

我将使用Apache Collections Lazy Map（将值初始化为0），并使用Apache Lang中的MutableIntegers作为该映射中的值。

最大的成本是必须在你的方法两次serach地图。 在我的，你只需要做一次。 只要获得该值（如果不存在，它将被初始化）并增加它。

Answer 20

Functional Java库的TreeMap结构在最新的中继头中有一个update方法：

 public TreeMap<K, V> update(final K k, final F<V, V> f) 

用法示例：

 import static fj.data.TreeMap.empty; import static fj.function.Integers.add; import static fj.pre.Ord.stringOrd; import fj.data.TreeMap; public class TreeMap_Update {public static void main(String[] a) {TreeMap<String, Integer> map = empty(stringOrd); map = map.set("foo", 1); map = map.update("foo", add.f(1)); System.out.println(map.get("foo").some());}} 

这个程序打印“2”。

Answer 21

@Vilmantas Baranauskas：关于这个答案，我会评论，如果我有重点，但我不知道。 我想要注意的是，定义的Counter类不是线程安全的，因为仅仅在没有同步value（）的情况下同步inc（）是不够的。 调用value（）的其他线程不保证能够看到该值，除非已经build立了与更新之前发生的关系。

Answer 22

您可以在Java 8中提供的Map接口中使用computeIfAbsent方法。

 final Map<String,AtomicLong> map = new ConcurrentHashMap<>(); map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); map.computeIfAbsent("B", k->new AtomicLong(0)).incrementAndGet(); map.computeIfAbsent("A", k->new AtomicLong(0)).incrementAndGet(); //[A=2, B=1] 

computeIfAbsent方法检查指定的键是否已经与一个值相关联？ 如果没有关联值，则尝试使用给定的映射函数来计算其值。 在任何情况下，它都会返回与指定键相关的当前（现有的或计算的）值，如果计算的值为空，则返回null。

在附注中，如果您遇到multithreading更新常见数据的情况，您可以查看LongAdder类。在较高的争用情况下，此类的预期吞吐量显着高于AtomicLong ，代价是空间消耗较高。

Answer 23

如果您正在使用Eclipse集合 ，则可以使用HashBag 。 这将是内存使用方面最有效的方法，并且在执行速度方面也将performance良好。

HashBag由一个MutableObjectIntMap支持，它存储的是原语ints而不是Counter对象。 这减less了内存开销并提高了执行速度。

HashBag提供了你需要的API，因为它是一个Collection ，它也允许你查询一个项目的出现次数。

下面是Eclipse Collections Kata的一个例子。

 MutableBag<String> bag = HashBag.newBagWith("one", "two", "two", "three", "three", "three"); Assert.assertEquals(3, bag.occurrencesOf("three")); bag.add("one"); Assert.assertEquals(2, bag.occurrencesOf("one")); bag.addOccurrences("one", 4); Assert.assertEquals(6, bag.occurrencesOf("one")); 

注意：我是Eclipse集合的提交者。

Answer 24

我不知道它是如何有效的，但下面的代码也是如此。你需要在开头定义一个BiFunction 。 另外，你可以使用这种方法做更多的事情。

 public static Map<String, Integer> strInt = new HashMap<String, Integer>(); public static void main(String[] args) { BiFunction<Integer, Integer, Integer> bi = (x,y) -> { if(x == null) return y; return x+y; }; strInt.put("abc", 0); strInt.merge("abc", 1, bi); strInt.merge("abc", 1, bi); strInt.merge("abc", 1, bi); strInt.merge("abcd", 1, bi); System.out.println(strInt.get("abc")); System.out.println(strInt.get("abcd")); } 

输出是

 3 1