Java 8 中 HashMap 的性能提升

HashMap是一個高效通用的數據結構，它在每一個Java程序中都隨處可見。先來介紹些基礎知識。你可能也知 道，HashMap使用key的hashCode()和equals()方法來將值劃分到不同的桶裡。桶的數量通常要比map中的記錄的數量要稍大，這樣 每個桶包括的值會比較少（最好是一個）。當通過key進行查找時，我們可以在常數時間內迅速定位到某個桶（使用hashCode()對桶的數量進行取模） 以及要找的對象。

Java 8 的 Nashorn 引擎  http://www.linuxidc.com/Linux/2014-03/98880.htm

這些東西你應該都已經知道了。你可能還知道哈希碰撞會對hashMap的性能帶來災難性的影響。如果多個hashCode()的值落到同一個桶內的 時候，這些值是存儲到一個鏈表中的。最壞的情況下，所有的key都映射到同一個桶中，這樣hashmap就退化成了一個鏈表——查找時間從O(1)到 O(n)。我們先來測試下正常情況下hashmap在Java 7和Java 8中的表現。為了能完成控制hashCode()方法的行為，我們定義了如下的一個Key類：

class Key implements Comparable<Key> {
private final int value;
Key(int value) {
this.value = value;
}
@Override
public int compareTo(Key o) {
return Integer.compare(this.value, o.value);
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass())
return false;
Key key = (Key) o;
return value == key.value;
}
@Override
public int hashCode() {
return value;
}
}

Key類的實現中規中矩：它重寫了equals()方法並且提供了一個還算過得去的hashCode()方法。為了避免過度的GC，我將不可變的Key對象緩存了起來，而不是每次都重新開始創建一遍：

class Key implements Comparable<Key> {
public class Keys {
public static final int MAX_KEY = 10_000_000;
private static final Key[] KEYS_CACHE = new Key[MAX_KEY];
static {
for (int i = 0; i < MAX_KEY; ++i) {
KEYS_CACHE[i] = new Key(i);
}
}
public static Key of(int value) {
return KEYS_CACHE[value];
}
}

現在我們可以開始進行測試了。我們的基准測試使用連續的Key值來創建了不同的大小的HashMap（10的乘方，從1到1百萬）。在測試中我們還會使用key來進行查找，並測量不同大小的HashMap所花費的時間：

import com.google.caliper.Param;
import com.google.caliper.Runner;
import com.google.caliper.SimpleBenchmark;
public class MapBenchmark extends SimpleBenchmark {
private HashMap<Key, Integer> map;
@Param
private int mapSize;
@Override
protected void setUp() throws Exception {
map = new HashMap<>(mapSize);
for (int i = 0; i < mapSize; ++i) {
map.put(Keys.of(i), i);
}
}
public void timeMapGet(int reps) {
for (int i = 0; i < reps; i++) {
map.get(Keys.of(i % mapSize));
}
}
}

 更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2014-04/100868p2.htm