Yige

// バケットの木化閾値。バケット内の要素数がこの値を超えると、赤黒木ノードに置き換える必要があります。
static final int TREEIFY_THRESHOLD = 8;
// 木の連結リスト復元閾値。拡張時、バケット内の要素数がこの値未満になると、木構造のバケット要素を連結リスト構造に戻します。
static final int UNTREEIFY_THRESHOLD = 6;
// ハッシュテーブルの最小木化容量。ハッシュテーブルの容量がこの値を超えると、テーブル内のバケットは木化できます。そうでない場合、バケット内の要素が多すぎると拡張され、木化されません。
// 拡張と木化の選択の衝突を避けるため、この値は4 * TREEIFY_THRESHOLD未満であってはなりません。
static final int MIN_TREEIFY_CAPACITY = 64;

// HashMapの容量が64未満の場合、赤黒木に直接変換するのではなく、拡張を選択します。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
            resize();
}
// TREEIFY_THRESHOLDはデフォルトで8です。
if (binCount >= TREEIFY_THRESHOLD - 1) {
    treeifyBin(tab, hash);
}

if (lc <= UNTREEIFY_THRESHOLD) {
    tab[index] = loHead.untreeify(map);
}

static int indexFor(int h, int length) {
    return h & (length-1);
}

/**
 * hash(key)メソッドを使用してkeyのハッシュ値を計算します。
 * getNode()メソッドを使用してnodeを取得します。
 * nodeがnullの場合はnullを返し、そうでない場合はnode.valueを返します。
 */
public V get(Object key) {
    Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * getNodeは以下のステップに分かれます:
 * 1. ハッシュテーブルが空であるか、keyに対応するバケットが空である場合、nullを返します。
 * 2. 空でない場合、バケット内の最初のノードが指定されたパラメータhashとkeyに一致する場合、このノードを直接返します。
 * 3. 最初のノードが一致しない場合、後続の検索を行います:
 *  3.1 現在のバケットが赤黒木を使用している場合、赤黒木のgetTreeNodeを呼び出してノード値を取得します。
 *  3.2 連結リスト構造の場合、連結リストを直接走査して検索します。
 * 4. ノードが見つかった場合はvalueを返し、そうでない場合はnullを返します。
 */
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    // ハッシュテーブルとkeyに対応するバケットが空でない場合
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 最適化ポイント 1: 不要なクエリを減らす
        // バケット内の最初のノードが指定されたパラメータhashとkeyに一致する場合、このノードを直接返します。
        if (first.hash == hash && // 常に最初のノードをチェック
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 最初のノードが一致しない場合、後続の検索を行います。
        if ((e = first.next) != null) {
            // 現在のバケットが赤黒木を使用している場合、赤黒木のgetTreeNodeを呼び出してノード値を取得します。
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            // 連結リスト構造の場合、連結リストを直接走査して検索します。
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

/**
 * putValメソッドは以下のステップに分かれます
 * 1. ハッシュテーブルが空である場合、resizeメソッドを呼び出して作成します。
 * 2. 指定されたkey値が衝突しない場合、すなわちハッシュ衝突がない場合、直接キーと値のペアを挿入します。
 * 3. 衝突がある場合、この衝突ノードを見つけます。
 *  3.1 最初のノードが一致した場合、記録します。そうでない場合は、さらに検索を続けます。
 *  3.2 現在が赤黒木構造の場合、putTreeValメソッドを呼び出して挿入します。
 *  3.3 連結リスト構造の場合、連結リストをループして検索し、最後まで見つからなかった場合は尾挿入法を使用してノードを挿入し、見つかった場合はこのノードを記録してループを終了します。
 * 4. 衝突ノードが見つかった場合、onlyIfAbsentがtrueであるかどうかを判断します。これは古い値を変更することを許可するかどうかを示します。
 * 5. HashMapの変更回数modCountと容量サイズsizeをインクリメントし、sizeがthresholdを超えた場合、臨界値に達したことを示し、拡張を行います。
 *
 * @param hash 指定されたkeyのhash値
 * @param key 指定されたkey
 * @param value 挿入する必要があるvalue値
 * @param e, 古い値の置き換えを許可しないことを示します。
 * @param evict HashMapが作成モードにあるかどうかを示します。
 * @return 指定されたkeyが存在する場合、古い値が置き換えられた場合はこの値を返し、そうでない場合はnullを返します。もちろんvalue値がnullである可能性もあります。
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // ハッシュテーブルが空である場合、resizeメソッドを呼び出して作成します。
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 指定されたkey値が衝突しない場合、すなわちハッシュ衝突がない場合、直接キーと値のペアを挿入します。
    // (n - 1) & hashはhash % nと等価ですが、ビット演算の方が速いです。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    // 衝突がある場合、この衝突ノードを見つけます。
    else {
        Node<K,V> e; K k;
        // 最初のノードが一致した場合、記録します。そうでない場合は、さらに検索を続けます。
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 現在が赤黒木構造の場合、putTreeValメソッドを呼び出して挿入します。
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 連結リスト構造の場合、連結リストをループして検索し、最後まで見つからなかった場合は尾挿入法を使用してノードを挿入します。
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 連結リストの長さが臨界値に達しているかどうかを確認し、達している場合は赤黒木構造に変換します。
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1は最初のため
                        treeifyBin(tab, hash);
                    break;
                }
                // 見つかった場合はこのノードを記録し、ループを終了します。
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        // 値がnullでない場合、衝突ノードが見つかったことを示します。
        if (e != null) { // 既存のキーのマッピング
            V oldValue = e.value;
            // onlyIfAbsentがtrueであるかどうかを判断します。これは古い値を変更することを許可するかどうかを示します。
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // sizeが臨界値に達したかどうかを判断し、拡張が必要です。
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

/**
 * tableを初期化または拡張します。拡張する場合、毎回容量が2倍になります。二進数計算の後、元のノードは元の位置にいるか、または「元の位置 + 旧容量」に割り当てられます。
 * resizeの手順の要約:
 * 1. 拡張後の容量と臨界値を計算します。
 * 2. HashMapの臨界値を更新します。
 * 3. 計算された拡張容量に基づいて新しい配列を作成し、HashMapのtable参照を新しい配列に指し示します。
 * 4. 古い配列の要素をtableにコピーします。
 */
final Node<K,V>[] resize() {
    // 新しいoldtab配列を作成して拡張前の配列tableを保存します。
    Node<K,V>[] oldTab = table;
    // 古い配列の長さを取得します。
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    // 古い配列の臨界値
    int oldThr = threshold;
    int newCap, newThr = 0;
    // 古い配列の容量が0より大きい場合
    if (oldCap > 0) {
        // 古い配列の容量が最大値を超える場合、臨界値を整数の最大値に設定します。
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 古い配列の容量がデフォルト容量（16）を超え、倍増後の新しい配列の容量が最大値未満の場合、古い配列の臨界値も倍増します。
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // 臨界値を倍増
    }
    // 古い容量 <= 0 かつ 臨界値 > 0 の場合
    else if (oldThr > 0) // 初期容量は閾値に置かれました
        // 新しい配列の容量を古い配列の臨界値に設定します。
        newCap = oldThr;
    // 古い容量 <= 0 かつ 臨界値 <= 0 の場合
    else {
        // 新しい容量をデフォルト値（16）に設定します。
        newCap = DEFAULT_INITIAL_CAPACITY;
        // 新しい臨界値をデフォルト容量 * デフォルト負荷係数（16 * 0.75）= 12に設定します。
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    // 上記の条件判断の中で、oldThr > 0の場合のみnewThr == 0です。
    if (newThr == 0) {
        // 合法的な判断を行い、新しい臨界値を設定します。
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
    // 新しい配列に古い配列の内容をコピーする操作を行います。
    @SuppressWarnings({"rawtypes","unchecked"})
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
    if (oldTab != null) {
        // 古いハッシュテーブルの各ノードを走査して配列にコピーします。
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            // eに古いノードの値を記録します。
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                // 古いバケットのストレージ衝突hash値の構造が赤黒木の場合
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 古いバケットのストレージ衝突hash値の構造が連結リスト構造の場合
                else { // 順序を保持
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    // java 7はwhileループ内で、単一の計算を行った後、単一で配列に挿入します。マルチスレッドの場合、環状問題が発生します。
                    // java 8は、連結リスト全体のwhileループが終了した後にのみ配列に値を割り当てるため、マルチスレッドの場合でも環状にはなりません。

                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // ノードは元の位置にあります。
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // ノードは「元の位置 + 旧容量」に割り当てられます。
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}