JavaのHashMapは効率的なキー値ペア管理を実現するためのコアデータ構造です。putメソッドの動作を理解するためには、ハッシュ値計算、衝突解決、テーブル拡張の仕組みを把握する必要があります。以下、処理の詳細を解説します。

基本処理フロー

putメソッドは指定されたキーと値をマップに追加または更新します。内部ではputValメソッドを呼び出し、ハッシュ値と制御フラグを渡します。

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

putValの詳細処理

putValメソッドはハッシュ値、キー、値、制御フラグを受け取り、以下のステップで処理を行います。

テーブル初期化

テーブルが未初期化または空の場合、resizeメソッドで初期化します。

if (buckets == null || (tableSize = buckets.length) == 0) {
    tableSize = (buckets = resize()).length;
}

インデックス算出

テーブルサイズが2の累乗である特性を利用し、(n-1) & hashで効率的にインデックスを計算します。

int index = (tableSize - 1) & hash;
if (buckets[index] == null) {
    buckets[index] = createNode(hash, key, value, null);
}

衝突解決

インデックス位置に既存エントリが存在する場合、衝突を解決します。

Node current = buckets[index];
if (current.hash == hash && (current.key == key || (key != null && key.equals(current.key)))) {
    existingNode = current;
} else if (current instanceof TreeNode) {
    existingNode = ((TreeNode)current).putTreeValue(this, buckets, hash, key, value);
} else {
    for (int chainLength = 0; ; chainLength++) {
        Node nextNode = current.next;
        if (nextNode == null) {
            current.next = createNode(hash, key, value, null);
            if (chainLength >= TREEIFY_THRESHOLD - 1) {
                convertToTree(buckets, hash);
            }
            break;
        }
        if (nextNode.hash == hash && (nextNode.key == key || (key != null && key.equals(nextNode.key)))) {
            break;
        }
        current = nextNode;
    }
}

値更新と挿入後処理

既存ノードが見つかった場合は値を更新し、新規挿入時はサイズを増加させて必要に応じてテーブルを拡張します。

if (existingNode != null) {
    V previousValue = existingNode.value;
    if (!onlyIfAbsent || previousValue == null) {
        existingNode.value = value;
    }
    afterNodeAccess(existingNode);
    return previousValue;
}
modCount++;
if (++size > threshold) {
    resize();
}
afterNodeInsertion(evict);
return null;

テーブル拡張メカニズム

resizeメソッドはテーブル容量を2倍に拡張し、既存エントリを再配置します。リハッシュ処理では元テーブルのエントリを新テーブルに再配置します。

Node[] previousTable = table;
int previousCapacity = previousTable != null ? previousTable.length : 0;
int previousThreshold = threshold;
int newCapacity, newThreshold = 0;
if (previousCapacity > 0) {
    if (previousCapacity >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return previousTable;
    }
    newCapacity = previousCapacity << 1;
    if (newCapacity < MAXIMUM_CAPACITY && previousCapacity >= MIN_INITIAL_CAPACITY) {
        newThreshold = previousThreshold << 1;
    }
} else if (previousThreshold > 0) {
    newCapacity = previousThreshold;
} else {
    newCapacity = DEFAULT_INITIAL_CAPACITY;
    newThreshold = (int)(DEFAULT_LOAD_FACTOR * newCapacity);
}
if (newThreshold == 0) {
    float newThresholdFloat = newCapacity * loadFactor;
    newThreshold = (newCapacity < MAXIMUM_CAPACITY && newThresholdFloat < MAXIMUM_CAPACITY) ?
        (int)newThresholdFloat : Integer.MAX_VALUE;
}
threshold = newThreshold;
Node[] newTable = new Node[newCapacity];
table = newTable;
if (previousTable != null) {
    for (int i = 0; i < previousCapacity; i++) {
        Node entry = previousTable[i];
        if (entry != null) {
            previousTable[i] = null;
            if (entry.next == null) {
                newTable[entry.hash & (newCapacity - 1)] = entry;
            } else if (entry instanceof TreeNode) {
                ((TreeNode)entry).split(this, newTable, i, previousCapacity);
            } else {
                Node lowerHead = null, lowerTail = null;
                Node higherHead = null, higherTail = null;
                do {
                    Node nextEntry = entry.next;
                    if ((entry.hash & previousCapacity) == 0) {
                        if (lowerTail == null) lowerHead = entry;
                        else lowerTail.next = entry;
                        lowerTail = entry;
                    } else {
                        if (higherTail == null) higherHead = entry;
                        else higherTail.next = entry;
                        higherTail = entry;
                    }
                    entry = nextEntry;
                } while (entry != null);
                if (lowerTail != null) {
                    lowerTail.next = null;
                    newTable[i] = lowerHead;
                }
                if (higherTail != null) {
                    higherTail.next = null;
                    newTable[i + previousCapacity] = higherHead;
                }
            }
        }
    }
}
return newTable;