java map更新value - 用Java增加Map值的最有效方法




13 Answers

一些测试结果

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

  • 我在问题中提出的“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倍)
  • 特洛夫 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();
}
map获取value map设置值

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

假设我使用一个Map(可能是一个HashMap)创建一个词频列表,其中每个键都是一个字符串,并且该字符被计数,并且该值是一个整数,每当找到该单词的一个标记时该值就会递增。

在Perl中,递增这样一个值将非常简单:

$map{$word}++;

但在Java中,它更复杂。 这是我目前正在做的事情:

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

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

更新:我已经做了几个答案的测试。 见下文。







谷歌Guava是你的朋友...

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

例如

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

也可以添加1以上的值:

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



你应该知道你最初的尝试

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

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

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

请注意,这将会产生类似的解决方案

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

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

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

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

为了完成答案(并且我首先忘记了这一点,感谢编辑功能!),最好的方式就是进入final变量,检查是否为null然后putput回到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())); 代替。




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

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

效益:

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

另一种方法是使用合并方法,但这仅仅是增加一个值而已。

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

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




而不是调用containsKey(),调用map.get并检查返回的值是否为null会更快。

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



有几种方法:

  1. 像使用Google收藏集中的套件一样使用Bag算法。

  2. 创建可在Map中使用的可变容器:


    class My{
        String word;
        int count;
    }

并用put(“word”,new My(“Word”)); 然后你可以检查它是否存在并在增加时增加。

避免使用列表滚动你自己的解决方案,因为如果你得到内部搜索和排序,你的表现会很糟糕。 第一个HashMap解决方案实际上是相当快的,但是像Google Collections那样的适当的解决方案可能会更好。

使用Google Collections计算单词,看起来像这样:



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


使用HashMultiset非常优雅,因为在计算单词时,bag-algorithm就是您所需要的。




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

如果你可以用这个变化重新运行你的性能测试,这将是有趣的。 这可能是最快的。

编辑:上面的模式对我来说工作得很好,但最终我更改为使用Trove的集合来减少我创建的一些非常大的地图中的内存大小 - 作为奖励,它也更快。

一个非常好的特性是adjustOrPutValue类有一个adjustOrPutValue调用,根据该键是否已经有一个值,将调用初始值或递增现有值。 这对于递增是完美的:

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



“放”需要“获得”(确保没有重复的键)。
所以直接做一个“放”,
并且如果有以前的值,则添加一个:

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
}

注意:这段代码不是线程安全的。 使用它来构建然后使用地图,而不是同时更新它。

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

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



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

最大的成本是不得不在你的方法中两次扫描地图。 在我的,你只需要做一次。 只需获取值(如果不存在,它将被初始化)并增加它。




@Vilmantas Baranauskas:关于这个答案,我会评论我是否有重点,但我不这样做。 我想要注意的是Counter类定义的不是线程安全的,因为仅仅在没有同步value()的情况下同步inc()是不够的。 其他调用value()的线程不保证能够看到该值,除非已经与更新建立了事前关系。




您可以在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。

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




由于很多人在Groovy的答案中搜索Java主题,因此您可以在Groovy中执行以下操作:

dev map = new HashMap<String, Integer>()
map.put("key1", 3)

map.merge("key1", 1) {a, b -> a + b}
map.merge("key2", 1) {a, b -> a + b}



Related

java optimization collections