HashMap 底层原理详解：put 流程、扩容与红黑树（JDK 1.8）

HashMap 是 Java 日常开发中使用频率最高的集合类之一，也是面试中几乎必问的“老熟人”。很多人能说出“数组加链表”，但一旦追问 hash 扰动怎么算、链表什么时候转红黑树、扩容时元素怎么迁移、为什么默认负载因子是 0.75，就答不上来了。本文以 JDK 1.8 为准，把 HashMap 的核心原理一次讲透。

一、整体结构：数组 + 链表 + 红黑树

JDK 1.8 的 HashMap 底层是一个 Node[] table 数组，数组的每个下标上挂着一个链表；当某个桶位上的链表长度太长（默认超过 8）且数组容量不小于 64 时，链表会升级成红黑树，把查找从 O(n) 降到 O(log n)。

// 简化后的存储节点（1.8 实际是 Node / TreeNode）
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // key 扰动后的哈希值
    final K key;
    V value;
    Node<K,V> next;   // 拉链法，指向下一个节点
}

二、三个关键默认值

为什么负载因子是 0.75？这是时间开销与空间开销的折中：太小（如 0.5）导致频繁扩容浪费空间；太大（如 1）哈希冲突严重、链表变长，查找效率下降。0.75 是官方经过泊松分布推算出的近似最优值——在理想随机哈希下，桶中链表长度达到 8 的概率约为千万分之六，所以 8 作为树化阈值非常安全。

三、hash 扰动函数：为什么 key.hashCode() 还要再算一次

定位数组下标用的是 (n - 1) & hash（n 为容量）。如果直接用 hashCode()，低 16 位完全相同的两个对象（例如 Float 类型整数部分相同但小数位不同的值）会全部撞到同一个桶。因此 JDK 把高 16 位“异或”到低 16 位，让高位也参与散列：

static final int hash(Object key) {
    int h;
    // 高 16 位和低 16 位异或，让哈希值分布更均匀
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 数组下标计算（put 与 get 中都出现）
i = (n - 1) & hash;

这里能直接用 & 代替取模 % 的前提是 容量 n 必须是 2 的幂：n - 1 的二进制全是低位的 1，(n - 1) & hash 等价于 hash % n，但位运算快得多。这就是为什么 HashMap 规定容量必须是 2 的幂，也是你传入非 2 的幂初始容量时（如 new HashMap(15)），它也会自动帮你 向上取整到最近的 2 的幂（16）。

四、put 方法完整执行流程

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    // 1. 数组为空或长度为 0，先调用 resize() 初始化（默认 16）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 下标处没有元素：直接 new 一个 Node 放进去
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 3. 发生哈希冲突，走链表或红黑树分支
        Node<K,V> e; K k;
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;                       // 第一个节点 key 就相同：覆盖
        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) // 长度到 8：尝试树化
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;                            // 链表中找到相同 key：跳出待覆盖
                p = e;
            }
        }
        if (e != null) {                  // 4. key 已存在：覆盖 value 并返回旧值
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // 5. 新增了一个节点，判断是否触发扩容（size > threshold）
    if (++size > threshold)
        resize();
    return null;
}

把流程提炼成一句话：先算下标，没冲突直接放；有冲突走链表/红黑树，key 相同就覆盖；放完检查 size 是否超过 threshold，超过就扩容。

五、get 方法流程

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
        // 先比较第一个节点（大多数情况一次命中）
        if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 红黑树走树查找，链表则顺序遍历
        if ((e = first.next) != null) {
            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;
}

六、扩容 resize：JDK 1.8 的高低位迁移

扩容发生在 size > threshold 时，新容量是旧容量的 2 倍，同时 threshold = newCap * loadFactor。扩容必须重新散列所有节点，而 1.8 做了一个精巧的优化：

因为新容量是 2 倍，oldCap 恰好是 2 的幂，元素重新定位时只需要看它哈希值里“新增的那一位”是 0 还是 1：

• 新增位为 0：留在原下标 i；
• 新增位为 1：移动到 i + oldCap。

// resize() 中迁移链表的典型片段（经过简化）
do {
    next = e.next;
    // e.hash 与 oldCap 做 & 运算，判断高位是否为 1
    if ((e.hash & oldCap) == 0) {
        // 低位：留在原位置
        if (loTail == null) loHead = e; else loTail.next = e;
        loTail = e;
    } else {
        // 高位：移动到 i + oldCap
        if (hiTail == null) hiHead = e; else hiTail.next = e;
        hiTail = e;
    }
} while ((e = next) != null);

这样迁移时不需要重新计算每个 key 的 hashCode，只用一次位运算就把一条链表劈成“低位链”和“高位链”两段，JDK 1.7 中那种“每个元素都重新取模再头插”的低效写法被彻底抛弃。

顺带解释一个经典考点：JDK 1.7 扩容采用头插法，并发扩容时两个线程可能把链表做成环，之后 get 一个不存在的 key 会无限循环（CPU 100%）。JDK 1.8 改成尾插法，从机制上消除了循环链表问题——但 HashMap 仍然不是线程安全的，并发写仍会丢数据，并发场景请使用 ConcurrentHashMap。

七、key 的要求：equals 与 hashCode 契约

HashMap 判断“是不是同一个 key”用的是：hash 相同 && (key == key || key.equals(k))。所以自定义对象做 key 时必须重写 equals 和 hashCode，并且遵守约定：

• equals 相等的两个对象，hashCode 必须相等（否则 equals 相同却定位到不同桶，get 永远拿不到）；
• hashCode 相等的两个对象，equals 可以不等（哈希冲突，落到同一桶里用 equals 区分）；
• 放进 HashMap 后不要再修改 key 的 hashCode（String、Integer 等不可变类天然安全，这也是推荐用它们做 key 的原因）。

八、JDK 1.7 与 1.8 对比 & 与 ConcurrentHashMap 对比

ConcurrentHashMap（1.8）放弃了 JDK 1.7 的 Segment 分段锁，改为 CAS + synchronized 锁桶头节点：写入时先 CAS 尝试，失败再对桶上锁，锁粒度从“一段”细化为“一个桶”，并发度大幅提升，且支持 size 等操作的并发统计。日常被问“为什么不用 HashTable”——HashTable 所有方法都加同一把锁，读多写少时性能远不如 ConcurrentHashMap。

九、高频面试题速答

• 为什么 HashMap 的容量必须是 2 的幂？ 让 (n-1) & hash 等价于取模且性能更高，同时扩容时元素只用判断一位就能完成迁移。
• 为什么链表长度到 8 才转红黑树？ 泊松分布显示理想哈希下桶内 8 个节点的概率约 0.0000006，8 是极安全的阈值，树化本身有维护成本，尽量避免触发。
• 为什么树化还要要求容量 ≥ 64？ 容量太小时应该优先扩容让链表变短，而不是急着树化。
• put 一个已存在的 key 返回什么？ 返回被覆盖的旧 value；新增时返回 null。
• HashMap 能否存 null？ key 和 value 都允许 null，null key 固定落在下标 0 的桶（hash=0）。
• 为什么 Integer/String 适合做 key？ 不可变，hashCode 稳定不随使用而变，且实现已经足够散列。

记住：源码里没有魔法，每个“神奇数字”（0.75、8、64、16）背后都是统计与工程权衡。把上面这条线串起来，HashMap 相关问题就能从容应对。