在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框架并使用其他东西？

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

Answer 1

一些测试结果

我已经为这个问题得到了很多好的答案 - 感谢大家 - 所以我决定运行一些测试并找出哪种方法实际上最快.我测试的五种方法是:

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

方法

这就是我做的......

1. 创建了五个相同的类,除了下面显示的差异.每个类都必须执行我所呈现的场景的典型操作:打开10MB文件并读入,然后执行文件中所有单词令牌的频率计数.由于这平均只花了3秒钟,我让它执行频率计数(不是I/O)10次.
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方法最具吸引力,因为它不需要加载任何第三方类.因此,除非我发现它的问题,这是我最有可能的方式.

代码

以下是每种方法的关键代码.

的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

好的,可能是一个老问题,但Java 8有一个更短的方法:

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

它的作用:如果key不存在,则将1作为值,否则将1加到与key相关的值.更多信息在这里

Answer 3

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 4

谷歌番石榴是你的朋友......

......至少在某些情况下.他们有这个漂亮的AtomicLongMap.特别好,因为你在地图上处理的价值很长.

例如

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

也可以为值添加多于1:

map.getAndAdd(word, 112L); 

Answer 5

@Hank Gay

作为我自己(相当无用)评论的后续行动:Trove看起来像是要走的路.如果出于某种原因,你想坚持使用标准的JDK,ConcurrentMap和AtomicLong的可以使代码一个微小的一点更好,但情况因人而异.

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

将1作为地图中的值保留foo.实际上,增加对线程的友好性就是这种方法必须推荐的.

Answer 6

查看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

有类似Map的方法来迭代键/条目等.在内部,实现当前使用a HashMap<E, AtomicInteger>,所以你不会招致拳击费用.

Answer 7

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

这就是你用简单的代码增加一个值的方法.

效益:

• 不为mutable int创建另一个类
• 短代码
• 容易明白
• 没有空指针异常

另一种方法是使用合并方法,但这对于增加值来说太多了.

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

建议:在大多数情况下,您应该关注代码可读性而不是小的性能提升.

Answer 8

你应该知道你原来的尝试

int count = map.containsKey(word) ? map.get(word) : 0;

在地图上包含两个可能很昂贵的操作,即containsKey和get.前者执行的操作可能与后者非常相似,所以你要做两次同样的工作!

如果查看Map的API,get操作通常会null在地图不包含所请求的元素时返回.

请注意,这将成为一个解决方案

map.put( key, map.get(key) + 1 );

危险的,因为它可能产生NullPointerExceptions.你应该先检查一下null.

还要注意,这非常重要,根据定义,HashMaps 可以包含nulls.所以不是每个回复的人null都说"没有这样的元素".在这方面,containsKey表现不同从get在实际告诉你是否有这样的元素.有关详细信息,请参阅API.

但是,对于您的情况,您可能不想区分存储null和"noSuchElement".如果您不想许可,null您可能更喜欢Hashtable.使用其他答案中已经提出的包装库可能是手动处理的更好解决方案,具体取决于应用程序的复杂程度.

为了完成答案(我忘了先把它放进去,多亏了编辑功能!),本地做的最好的方法是get变成一个final变量,检查null并put重新输入1.变量应该是final因为它无论如何都是不可变的.编译器可能不需要这个提示,但它更清晰.

final HashMap map = generateRandomHashMap();
final Object key = fetchSomeKey();
final Integer i = map.get(key);
if (i != null) {
    map.put(i + 1);
} else {
    // do something
}

如果你不想依赖自动装箱,你应该说出类似的话map.put(new Integer(1 + i.getValue()));.

Answer 9

另一种方法是创建一个可变整数:

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

当然这意味着创建一个额外的对象,但与创建一个Integer(即使使用Integer.valueOf)相比,开销不应该那么多.

Answer 10

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

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,则返回null.

另外,如果您有多个线程更新公共总和的情况,您可以查看LongAdder类.在高争用情况下,此类的预期吞吐量明显高于AtomicLong,但代价是空间消耗较高.

Answer 11

内存轮换可能是一个问题,因为每次大于或等于128的int会导致对象分配(请参阅Integer.valueOf(int)).虽然垃圾收集器非常有效地处理短期对象,但性能会受到一定程度的影响.

如果您知道所做的增量数量将大大超过键的数量(在这种情况下为单词),请考虑使用int holder.Phax已经为此提供了代码.这里再次进行两次更改(holder类为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();
}

如果您需要极高的性能,请寻找直接针对原始值类型的Map实现.jrudolph提到了GNU Trove.

顺便说一下,这个主题的一个好的搜索词是"直方图".

Answer 12

很简单，使用内置函数Map.java如下

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

Answer 13

我建议使用 Java 8 Map::compute()。它还考虑了密钥不存在的情况。

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

Answer 14

而不是调用containsKey(),只需调用map.get并检查返回的值是否为null.

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