Help us understand the problem. What is going on with this article?

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すると全てのビットが立つので,下位ビットを残す演算になっている様子。

ma38su
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした