你也許經(jīng)常需要一個計數(shù)器來了解數(shù)據(jù)庫或文本文件中一些事務(wù)出現(xiàn)的頻率（例如單詞）填抬。通過在Java中計數(shù)器可以通過HashMap可以輕松實現(xiàn)計數(shù)器。本文比較了實現(xiàn)不同的計數(shù)器方法。
更新： 查看Java8 計數(shù)器，寫一個計數(shù)器現(xiàn)在只是簡單的2行代碼菱阵。
1.基本計數(shù)器
樸素計數(shù)器可以如下實現(xiàn):
String s = "one two three two three three";
String[] sArr = s.split(" ");
//naive approach
HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (String a : sArr) {
if (counter.containsKey(a)) {
int oldValue = counter.get(a);
counter.put(a, oldValue + 1);
} else {
counter.put(a, 1);
}
}
在每個循環(huán)中，你檢查key是否存在绊诲。如果是送粱，則將舊值增加1，否則將其設(shè)置為1掂之，這種方法很簡單直接抗俄，但是它不是最有效的方法脆丁，由于以下方法，該方法被認為是低效的动雹。
- containsKey()槽卫，get（）在一個key存在時候，被調(diào)用了兩次胰蝠，這意味了搜索了Map兩次歼培。
- 既然Integer是不可變的，每次循環(huán)將創(chuàng)建一個新的值來替代增加的舊值茸塞。
2.更好的計數(shù)器
自然地躲庄，我們希望有一個可變的Integer來避免穿件很多Integer對象。一個可變的Integer 類如下定義：
class MutableInteger {
private int val;
public MutableInteger(int val) {
this.val = val;
}
public int get() {
return val;
}
public void set(int val) {
this.val = val;
}
//used to print value convinently
public String toString(){
return Integer.toString(val);
}
}
計數(shù)器代碼改變?nèi)缦拢?/p>
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
if (newCounter.containsKey(a)) {
MutableInteger oldValue = newCounter.get(a);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(a, new MutableInteger(1));
}
}
這是更好钾虐，因為不需要創(chuàng)建許多Integer對象噪窘。但是存在key鍵，仍然搜索兩次效扫。
3. 更高效計數(shù)器
HashMap.put(key, value) 方法返回鍵的當(dāng)前值倔监。這是有用的，因為我們可以使用舊值的引用來更新值菌仁，而不用再搜索一次浩习。
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
for (String a : sArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(a, initValue);
if(oldValue != null){
initValue.set(oldValue.get() + 1);
}
}
4.性能表現(xiàn)差異
為測試三種不同方法的性能，使用下面的代碼济丘，性能測試100萬次谱秽，原始結(jié)果如下：
Naive Approach : 222796000
Better Approach: 117283000
Efficient Approach: 96374000
差別是顯著的，223 vs 117 vs 96 基礎(chǔ)計數(shù)器和高效計數(shù)器相差巨大闪盔，說明創(chuàng)建對象是昂貴的弯院。
String s = "one two three two three three";
String[] sArr = s.split(" ");
long startTime = 0;
long endTime = 0;
long duration = 0;
// naive approach
startTime = System.nanoTime();
HashMap<String, Integer> counter = new HashMap<String, Integer>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
if (counter.containsKey(a)) {
int oldValue = counter.get(a);
counter.put(a, oldValue + 1);
} else {
counter.put(a, 1);
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Naive Approach : " + duration);
// better approach
startTime = System.nanoTime();
HashMap<String, MutableInteger> newCounter = new HashMap<String, MutableInteger>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
if (newCounter.containsKey(a)) {
MutableInteger oldValue = newCounter.get(a);
oldValue.set(oldValue.get() + 1);
} else {
newCounter.put(a, new MutableInteger(1));
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Better Approach: " + duration);
// efficient approach
startTime = System.nanoTime();
HashMap<String, MutableInteger> efficientCounter = new HashMap<String, MutableInteger>();
for (int i = 0; i < 1000000; i++)
for (String a : sArr) {
MutableInteger initValue = new MutableInteger(1);
MutableInteger oldValue = efficientCounter.put(a, initValue);
if (oldValue != null) {
initValue.set(oldValue.get() + 1);
}
}
endTime = System.nanoTime();
duration = endTime - startTime;
System.out.println("Efficient Approach: " + duration);
在你進行計數(shù)的時候，可能需要Map的按值排序泪掀，可以看下Map按照值排序.
5.來自Keith解決方案
添加了幾個測試：
1） 重構(gòu)“更好方法”只是調(diào)用get而不是containsKey听绳，通常你想要的元素在HashMap，只需要搜索一次异赫。
2）添加一個AtomicInteger來進行測試椅挣，
3）與單獨的int數(shù)組相比，根據(jù)http://amzn.com/0748614079使用較少的內(nèi)存
我運行測試程序三次塔拳，并且采取最小的值鼠证，以消除與其他程序的方差。注意靠抑，你不能在程序中這樣做量九，這樣結(jié)果可能受GC影響而不同。
Naive: 201716122
Better Approach: 112259166
Efficient Approach: 93066471
Better Approach (without containsKey): 69578496
Better Approach (without containsKey, with AtomicInteger): 94313287
Better Approach (without containsKey, with int[]): 65877234
更好的辦法（沒有containsKey）:
HashMap<String, MutableInteger> efficientCounter2 = new HashMap<String, MutableInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
MutableInteger value = efficientCounter2.get(a);
if (value != null) {
value.set(value.get() + 1);
} else {
efficientCounter2.put(a, new MutableInteger(1));
}
}
}
更好的辦法（沒有containsKey，用AutomicInteger）：
HashMap<String, AtomicInteger> atomicCounter = new HashMap<String, AtomicInteger>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
AtomicInteger value = atomicCounter.get(a);
if (value != null) {
value.incrementAndGet();
} else {
atomicCounter.put(a, new AtomicInteger(1));
}
}
}
更好的方法（沒用containsKey ,用int[]）:
HashMap<String, int[]> intCounter = new HashMap<String, int[]>();
for (int i = 0; i < NUM_ITERATIONS; i++) {
for (String a : sArr) {
int[] valueWrapper = intCounter.get(a);
if (valueWrapper == null) {
intCounter.put(a, new int[] { 1 });
} else {
valueWrapper[0]++;
}
}
}
Guava的MultiSet可能更快荠列。
6 .結(jié)論
