JavaのHashMapのソースを読む

Java

いい加減ハッシュテーブルは実装レベルで理解しくべきということで，ざっと読んだときの気付きをメモしておく。10年前は読めなかったけど，今回はさくっと読めた。(読んだのは，Adopt Open JDK 13)

テーブル内部では以下のクラスでデータが管理されていた。要するにClosed Addressingで実装されている。

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        /** 中着 */
    }

余談だが，Eclipse Collection(10.1)のUnifiedMapもOpen Addressingだったが，こちらはポインタでチェインせずに配列でチェインしていた。Open Addressingのようにメモリのキャッシュを効かせたいことが理由の様子。

ハッシュ値の計算。 要素数が少ないときには，下位ビットだけで格納場所が決まってしまうことを避けるため，上位ビットも使えるように下位16bitに上位16bitのXORをとっていた。

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

ハッシュテーブルの引き方。 テーブルの要素数nから1引いたものとAND演算した値をindexとしていた。

    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);

ちなみにテーブルの要素数(上記のtab.length)数は，2の倍数になっているようで，そこから-1すると全てのビットが立つので，下位ビットを残す演算になっている様子。