JavaのHashMapのソースを読む

いい加減ハッシュテーブルは実装レベルで理解しくべきということで，ざっと読んだときの気付きをメモしておく。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すると全てのビットが立つので，下位ビットを残す演算になっている様子。