如何高效的实现一个计数器map
发布网友
发布时间：2022-05-02 00:53
共1个回答
热心网友
时间：2022-04-22 09:32
面对这样一个基本需求，可能有很多种实现。比如最基本的使用jdk的map直接实现——value是一个integer或者long。其基本代码型如下：
1: final Map<String, Integer> freq = new HashMap<String, Integer>();
2: int count = freq.containsKey(word) ? freq.get(word) : 0;
3: freq.put(word, count + 1);
逻辑简单，判断是否存在，是则get取值，否则为0，再put进去一个加1后的值。总共要contain判断，get，put做三次方法调用。
当然进一步我们可以把contain判断去掉，代码如下：
1: final Map<String, Integer> freq = new HashMap<String, Integer>();
2: Integer count = freq.get(word);
3: if (count == null) {
4: freq.put(word, 1);
5: } else {
6: freq.put(word, count + 1);
7: }
一般情况，我们做到这个地步，多数人对其逻辑已经满足，简单性能也能接受，试着想一下，难道不是这样吗？get加put，解决了。
当然这样的实现还不够高效，于是我们开始去尝试实现或寻找更高效的方法，看看开源的集合类库是否有需要的：
有个Trove，可以让我们参考一下：
1: final TObjectIntHashMap<String> freq = new TObjectIntHashMap<String>();
2: freq.adjustOrPutValue(word, 1, 1);
这样做，非常优雅啊，性能如何呢？不知道，需要看源码了解细节。那再看看大名鼎鼎的guava如何呢？
1: AtomicLongMap<String> map = AtomicLongMap.create();
2: map.getAndIncrement(word);
实现依然优雅，但是，但是看这名字，再看源码，好吧，线程安全的，支持并发，这不好搞了，我们场景需要吗？不需要的话直觉告诉我们这肯定是“慢”的。再找：
1: Multiset<String> bag = HashMultiset.create();
2: bag.add(word);
这个看上去合适了，bag的实现明显好很多，而且从语义理解上，这样的接口更容易让人理解。
那么这些方法，性能如何呢？做了个简单的比较，将26个英文字母做key，均匀循环若干次比较各个方法的效率（单纯时间效率），而且时间不统计构建开销。外加了一个线程安全版的concurrentMap实现，而其实google的guava里的AtomicLongMap也是包装了juc的concurrentMap而已。里面有最终极的MutableInt方法，找找看吧，性能最好的就是它了。
