HashMapは効率的で汎用性の高いデータ構造で、Javaのプログラムには必ずと言っていいほど登場します。基本的なことから始めましょう。ご存知のように、HashMapはキーのhashCode()メソッドとequals()メソッドを使用して値をバケットにグループ化します。通常、バケットの数はマップのレコード数より少し多く、バケットに含まれる値は少なくなります。キーで検索すると、バケツと探しているオブジェクトを一定の時間ですばやく見つけることができます。
これらのことはすでにご存知でしょう。また、ハッシュの衝突が hashMap のパフォーマンスに悲惨な影響を与えることもご存知でしょう。複数の hashCode() の値が同じバケツに入ると、連鎖したテーブルに格納されます。最悪の場合、すべてのキーが同じバケツにマップされ、ハッシュマップは連鎖テーブルになり、ルックアップ時間はO(1)からO(n)になります。まず、Java 7とJava 8でhashmapが通常の状態でどのように振る舞うかをテストしてみましょう。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 を作成します。また、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));
}
}
}
興味深いことに、Java 8のこの単純なHashMap.get()は、Java 7よりも20%高速です。HashMapに100万件のレコードがあるにもかかわらず、1回のクエリにかかった時間は10ナノ秒未満、つまり私のマシンではおよそ20CPUサイクルでした。 かなり印象的です！しかし、それは測定したいものではありません。
いつも同じ値を返す、本当に悪いキーがあるとします。これはHashMapを使うべきでない最悪のシナリオです。
class Key implements Comparable<Key> {
//...
@Override
public int hashCode() {
return 0;
}
}
Java 7の結果は予想通りでした。HashMapのサイズが大きくなるにつれて、get()メソッドのオーバーヘッドも大きくなりました。すべてのレコードは同じバケット内の超長いリンクリストにあるので、平均して、1つのレコードに対するクエリはリストの半分をトラバースする必要があります。ですから、グラフからわかるように、O(n)の時間複雑度を持ちます。
しかし、Java 8の方がはるかに性能がいいです！対数曲線なので、桁違いの性能です。この同じベンチマークは、ハッシュの衝突が激しいという事実にもかかわらず、JDK 8ではO(logn)の時間複雑度を持ちます。JDK 8の曲線は単体で見れば明らかで、対数線形分布です：
Big-O表記が使われているにもかかわらず、なぜこれほど大きな性能向上があるのでしょうか？実はこの最適化はJEP-180で言及されています。バケツ内のレコードが大きすぎる場合、HashMap は動的にそれを特殊化したトレマップ実装に置き換えます。これにより、O(n)という悪い結果ではなく、O(logn)という良い結果が得られます。どのように動作するのですか？前の衝突したKEYに対応するレコードはリンクリストの後ろに追加されます。しかし、この閾値を超えると、HashMapはハッシュ値をツリーの分岐変数として使用し、リストをバイナリツリーにアップグレードし始めます。 2つのハッシュ値が等しくないが同じバケツを指す場合、大きい方が右のサブツリーに挿入されます。ハッシュ値が等しい場合、HashMapはキー値がComparableインタフェースを実装したものであることを望みます。これはHashMapのキーには必須ではありませんが、実装しておくのがベストです。このインターフェイスを実装していない場合、深刻なハッシュの衝突が発生したときにパフォーマンスが向上することは期待できません。
この性能向上の用途は何でしょうか？悪意のあるプログラムがハッシュアルゴリズムが使用されていることを知ると、大量のリクエストを送信し、深刻なハッシュの衝突を引き起こす可能性があります。JDK 8のO(n)からO(logn)への飛躍は、同様の攻撃を効果的に防ぐとともに、HashMapのパフォーマンスをわずかに予測しやすくします。この機能強化によって、最終的に上司がJDK 8へのアップグレードに同意してくれることを期待しています。
Intel Core i7-3635QM @ 2.4GHz、8GBのRAM、SSDハードドライブ、64ビットWindows 8.1、デフォルトのJVMパラメータで動作。
