函数Java库的TreeMap数据结构在最新的主干头中有一个更新方法:

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”。

部分测试结果

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

我在问题中提到的“ContainsKey”方法 Aleksandar Dimitrov建议的“TestForNull”方法 Hank Gay建议的“AtomicLong”方法 即鲁道夫提出的“宝藏”方法 phax.myopenid.com建议的“MutableInt”方法

方法

我是这么做的……

created five classes that were identical except for the differences shown below. Each class had to perform an operation typical of the scenario I presented: opening a 10MB file and reading it in, then performing a frequency count of all the word tokens in the file. Since this took an average of only 3 seconds, I had it perform the frequency count (not the I/O) 10 times. timed the loop of 10 iterations but not the I/O operation and recorded the total time taken (in clock seconds) essentially using Ian Darwin's method in the Java Cookbook. performed all five tests in series, and then did this another three times. averaged the four results for each method.

结果

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

正如预期的那样，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);

测试空

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

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

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)相比，开销不应该那么多。

作为我自己评论的后续: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的map中保留1作为值。实际上，增加线程的友好性是这种方法所推荐的。

MutableInt方法的一个变体可能更快，如果有点hack，是使用一个单元素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的集合来减少我正在创建的一些非常大的地图的内存大小——作为奖励，它也更快。

一个非常好的特性是TObjectIntHashMap类有一个单独的adjustOrPutValue调用，根据该键是否已经有一个值，它将放置一个初始值或增加现有值。这对于增量来说是完美的:

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

谷歌集合HashMultiset: -使用起来相当优雅 —但会消耗CPU和内存

最好是有这样一个方法:Entry<K,V> getOrPut(K); (美观，成本低)

这样的方法只计算哈希和索引一次， 然后我们可以对元素做我们想做的 (替换或更新值)。

更优雅: -取一个HashSet<Entry> -扩展它，以便get(K)在需要时放置一个新的条目 -入口可以是你自己的对象。 ——> (new MyHashSet()).get(k).increment();