HashMapとConcurrentHashMap - Servlet Garden ＠はてな

HashMapのデータ構造がどのようになっているかなんてすっかり忘れているし、java.util.concurrentHashMapはパフォーマンスがいいと言われているのはなぜなのだろうかと思い、ソースコードを眺めてみました。HashMapやらHashtableやらのおさらいをかねて調べたことをメモします。
まずはデータ構造の基本的な概念はこんな感じ。

binとかbucketとか呼ばれている複数の入れ物(配列)にオブジェクトを詰めていきます。入れ物の上にある数字はhash値で、入れ物に詰めるオブジェクトから得られる数値や文字列から計算したものです。例えば、hash値を計算するアルゴリズムが

A->1, B->2, C->3, D->4, ..., Z->26と置き換えて全部足したら16で割った余りを求める




















































































-









































hashCode   hash値の計算



















































































-









































ALICE      (1 + 12 + 9 + 3 + 5) % 16 = 14
BOB        (2 + 15 + 2) % 16 = 3
CHRIS      (3 + 8 + 18 + 9 + 19) % 16 = 3



















































































-

だったとすると、14番めの入れ物にALICEオブジェクトを入れて、3番めの入れ物にBOBとCHRISのオブジェクトをいれます。全部で16個もあるのに他の入れ物は空です。
この入れ物に入っているオブジェクトを見つけ出すときは、hash値を計算して、まず何番めの入れ物に入っているかを見つけ、次にその入れ物の中のオブジェクトを一つ一つ調べていって欲しいオブジェクトかどうかを捜し当てるようになっています。Javaではjava.lang.Object#hashCode()メソッドで得られる数値からhash値を計算して、java.lang.Object#equals()メソッドを使って該当するオブジェクトかどうかを調べています。
当然、equals()メソッドを実行する回数は少ない方がいいので、入れ物が16あったら、オブジェクトが20個入っているところと12個入っているところがあるだけで他は空、よりも均等に2個ずつ入っている方が速く見つけだせる場合が多いはずです。ということで、ConcurrentHashMapはhash値の計算も工夫していました。こういうところもパフォーマンスに貢献しているのでしょう。

HashMapの場合:
    static int hash(int h) {
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

ConcurrentHashMapの場合:
    private static int hash(int h) {
        // Spread bits to regularize both segment and index locations,
        // using variant of single-word Wang/Jenkins hash.
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

さて、これはつまり、

    public int hashCode() {
        return 12345;
    }

のように、インスタンスが違うのにhashCode()で帰ってくる値が同じだとすると、ConcurrentHashMapさんがどんなにがんばっていいアルゴリズムを提供してくれていても、オブジェクトはいつも同じ入れ物に入ってしまって何度もequals()メソッドを繰り返すはめになるわけです。hashCode()メソッドではできるだけ違う数字を返すようにこころがけたいものです。

hashCode()メソッドで適度にバラバラの数値が返ってきてうまく16個の入れ物に均等に詰められたとしても、一つ一つの入れ物にたくさんのオブジェクトが詰まっていると、順番にequals()を実行していくのでどうしても時間がかかります。そこで、ConcurrentHashMapでは各入れ物の中に仕切りを作って、もう一度hash値を使って入れる場所を振り分けていました。2次元配列になっているのですね。

ConcurrentHashMap.javaの一部:
        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

        HashEntry getFirst(int hash) {
            HashEntry tab = table;
            return tab[hash & (tab.length - 1)];
        }
        
        transient volatile HashEntry table;

仕切りで区切られた中のオブジェクトについてはHashMap同様、一つ一つequals()メソッドを実行して調べていきますが、getFirst()メソッドでいきなり目的のオブジェクトに行き着く可能性が大きくなる上に、仕切りの中のオブジェクトが減るのでequals()を実行する回数も減ると期待できます。このようなデータ構造からもConcurrentHashMapはパフォーマンスが向上しているのでしょう。