HashMap的扩容机制 - resize() 详解

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        // 初始化时扩容（第一次 put）
        n = (tab = resize()).length;
    // ... 哈希桶定位 ...
    if (++size > threshold) // 元素数量超过阈值
        resize(); // 触发扩容
    // ... 插入元素 ...
}

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
 
    // 1. 计算新容量和新阈值
    if (oldCap > 0) { // 非初始化扩容
        if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大容量，不再扩容
            threshold = Integer.MAX_VALUE;
            return oldTab;
        } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
            newThr = oldThr << 1; // 阈值翻倍
        }
    } else if (oldThr > 0) { // 初始化时指定了初始容量（如 new HashMap(100)）
        newCap = oldThr;
    } else { // 无参构造，初始化默认容量
        newCap = DEFAULT_INITIAL_CAPACITY; // 16
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 12
    }
 
    // 处理新阈值未设置的情况（如非默认初始化）
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    threshold = newThr;
 
    // 2. 创建新数组
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;
 
    // 3. 迁移旧数组元素
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null; // 释放旧数组引用，便于 GC
                if (e.next == null) { // 单个节点，直接放入新桶
                    newTab[e.hash & (newCap - 1)] = e;
                } else if (e instanceof TreeNode) { // 红黑树节点，调用 split 拆分
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                } else { // 链表节点，拆分为低位链和高位链
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 核心：通过位运算判断高位，拆分链表
                        if ((e.hash & oldCap) == 0) { // 低位链（原位置）
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        } else { // 高位链（原位置 + oldCap）
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                        e = next;
                    } while (e != null);
                    // 将拆分后的链表放入新桶
                    if (loTail != null) {
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

// 公式：initialCapacity = (int) (expectedSize / loadFactor) + 1
int expectedSize = 1000;
float loadFactor = 0.75f;
Map<String, Object> map = new HashMap<>((int) (expectedSize / loadFactor) + 1, loadFactor);

import java.util.HashMap;
import java.util.Map;
 
public class HashMapResizeDemo {
    public static void main(String[] args) {
        // 初始容量 4，负载因子 0.75 → 阈值 3
        Map<Integer, String> map = new HashMap<>(4, 0.75f);
 
        // 1. 插入 3 个元素，未触发扩容（size=3 < threshold=3？不，threshold=4*0.75=3 → size=3 等于阈值，put 第4个时触发）
        map.put(1, "A");
        map.put(2, "B");
        map.put(3, "C");
        System.out.println("插入3个元素后，容量：" + getCapacity(map) + "，size：" + map.size());
 
        // 2. 插入第4个元素，触发扩容（容量从4→8，阈值从3→6）
        map.put(4, "D");
        System.out.println("插入第4个元素后，容量：" + getCapacity(map) + "，size：" + map.size());
 
        // 3. 插入更多元素，观察红黑树转换（链表长度≥8且容量≥64时转换）
        for (int i = 5; i <= 100; i++) {
            map.put(i, "Val" + i);
        }
        System.out.println("插入100个元素后，容量：" + getCapacity(map) + "，size：" + map.size());
    }
 
    // 反射获取 HashMap 的容量（仅用于演示）
    private static int getCapacity(Map<?, ?> map) {
        try {
            java.lang.reflect.Field field = map.getClass().getDeclaredField("table");
            field.setAccessible(true);
            Object[] table = (Object[]) field.get(map);
            return table == null ? 0 : table.length;
        } catch (Exception e) {
            throw new RuntimeException(e);
        }
    }
}