HashMap 原理与源码分析

HashMap 是 Java 中使用最广的容器，也是面试中被追问得最深的类之一。很多人能背出"数组 + 链表 + 红黑树、初始容量 16、负载因子 0.75、扩容两倍"，但说不清为什么是这些数字、树化阈值为什么是 8、扩容时为什么能高效拆分。本文基于 JDK 8 与 JDK 17 的源码，把这些问题逐个落到代码行上。

一、数据结构：数组桶 + 链表 + 红黑树

HashMap 的主干是一个 Node 数组，称为 table。每个桶位存放一条链表，链表过长时转为红黑树。

table (长度 16)
[0] → null
[1] → Node(k1,v1) → Node(k2,v2) → null
[2] → null
...
[5] → TreeNode（红黑树，当链表长度 ≥ 8 且 table ≥ 64）
...
[15] → null

节点定义在 JDK 8 中分为两种：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;   // 扰动后的 hash
    final K key;
    V value;
    Node<K,V> next;   // 链表后继
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;   // 删除后需要退化为链表，因此保留前驱
    boolean red;
}

TreeNode 继承自 LinkedHashMap.Entry，因此它同时具备 next 和 prev，既能作为红黑树节点，也能在退化时快速串成链表。

关键字段还有三个：

transient Node<K,V>[] table;
transient int size;          // 实际键值对数量
final float loadFactor;      // 负载因子，默认 0.75
int threshold;               // 扩容阈值 = capacity * loadFactor

二、hash 扰动与定位

HashMap 不直接使用 hashCode()，而是做了一次高低位异或：

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

原因在于定位下标用的是 (n - 1) & hash。当 n 是 2 的幂时，n - 1 的低位全是 1，等价于取模，但只有低位参与运算。如果 hashCode 的低位分布不佳（很多对象的 hashCode 低位规律性强），冲突会急剧增加。把高 16 位右移后异或到低位，相当于让高位也参与下标计算，用一次移位和一次异或换来更好的离散度。

定位逻辑在 getNode 中：

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;
}

判断顺序值得注意：先比 hash，再比引用 ==，最后才调 equals。引用相等直接命中是最快的路径，equals 调用次数被压到最低。

三、put 的完整流程

putVal 是整个类的核心，可以拆成五步：

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. 懒初始化
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2. 桶为空，直接放
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 3. 桶首节点就是目标
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 4. 树节点走红黑树插入
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 5. 链表遍历，尾插
            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;
                p = e;
            }
        }
        if (e != null) { // 已存在 key，覆盖 value
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);   // 供 LinkedHashMap 使用
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

几个细节：

• JDK 8 改为尾插，JDK 7 是头插。头插在并发扩容时可能形成环形链表，导致 CPU 100%，尾插避免了这个问题，但 HashMap 依然不是线程安全的。
• 树化不是链表一到 8 就立即转，treeifyBin 里会先检查 tab.length，小于 64 时优先扩容而不是树化。
• 覆盖已有 key 时不会增加 size，也不会触发扩容。

treeifyBin 的判断值得单独看：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();                                  // 容量不足 64，先扩容
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null) hd = p;
            else { p.prev = tl; tl.next = p; }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab);                       // 真正构建红黑树
    }
}

先转成 TreeNode 双向链，再由 treeify 逐个插入并做变色、旋转。这样即使树化失败或后续退化，链表结构仍然完整。

四、扩容：2 倍容量与高低位拆分

resize() 是 HashMap 中最精妙的部分。容量翻倍后，每个元素的桶下标要么不变，要么变成"原下标 + 旧容量"。

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    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;           // 阈值也翻倍
    }
    // ... 省略按 threshold 反推容量的分支
    threshold = newThr;
    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;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;   // 单节点直接重算
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // 拆成 lo、hi 两条链
                    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) {    // 新增位为 0
                            if (loTail == null) loHead = e;
                            else loTail.next = e;
                            loTail = e;
                        } else {                          // 新增位为 1
                            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;
}

关键判断是 (e.hash & oldCap) == 0。旧容量是 2 的幂，其二进制只有一个 1，正好对应新容量参与取模的那一位。为 0 则下标不变，为 1 则下标加 oldCap。这样既不用重新计算 hash，也避免了 JDK 7 中每个节点重新取模的开销。

五、为什么是 16、0.75、8、64

HashMap 的注释里明确写了：在随机 hash 下，链表长度符合泊松分布，长度 8 的桶出现概率约为 0.00000006，几乎不可能。树化阈值设为 8 是为了防御恶意构造的 hash 冲突（哈希碰撞攻击），而不是常规场景。

树化的收益也不是免费的。TreeNode 的内存占用约为普通 Node 的两倍，插入和删除需要维护红黑树的平衡，常数开销更大。所以阈值不能设得太低，否则正常业务里的轻微冲突都会触发树化，反而拖慢整体性能。6 与 8 之间留出的 1 个空档，是为了防止节点数在 7 和 8 之间反复抖动，造成树化与退化来回切换。

容量计算还有一个容易忽略的点：tableSizeFor 会把任意初始容量向上取整到 2 的幂。

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

所以 new HashMap<>(10) 的实际容量是 16，而不是 10。

六、并发场景分析

HashMap 在多线程下有三类典型问题：

1. 丢数据。两个线程同时往空桶写入，后写覆盖先写；size++ 非原子，最终数量偏小。
2. 死循环。JDK 7 头插法在并发扩容时可能让链表成环，get 时无限循环。JDK 8 改尾插后不再成环，但仍可能丢数据或读到不一致的中间状态。

JDK 7 成环的具体过程是：两个线程同时执行 transfer，线程 A 处理到一半被挂起，线程 B 完成迁移后，节点顺序已经反转；线程 A 恢复后按旧引用继续头插，把 a.next 指向 b，而 b.next 已指向 a，形成 a ⇄ b 的环。此后任何落到该桶的查询都会在这两个节点之间无限打转，CPU 直接飙满。这也是"HashMap 并发会导致 CPU 100%"这一说法的来源，JDK 8 虽然修掉了成环，但没有修掉数据竞争本身。

3. 红黑树结构破坏。并发 put 触发树化或 split 时，父子指针可能错乱，导致查询异常。

正确做法：

// 读多写少、允许弱一致
Map<String, Integer> map = new ConcurrentHashMap<>();
map.merge("k", 1, Integer::sum);

// 需要整体同步语义
Map<String, Integer> sync = Collections.synchronizedMap(new HashMap<>());
synchronized (sync) {   // 复合操作仍需外部加锁
    sync.put("k", sync.getOrDefault("k", 0) + 1);
}

ConcurrentHashMap 的 merge、compute、computeIfAbsent 都是原子操作，复合更新优先用它们，而不是 get 再 put。

七、常见坑 / 最佳实践

1. key 必须正确实现 hashCode 与 equals。只重写 equals 不重写 hashCode，两个"相等"的对象会落到不同桶，get 永远拿不到。用 IDE 或 Objects.hash 生成，且参与计算的字段要与 equals 一致。
2. 不要用可变对象作 key。key 放进 HashMap 后如果字段被修改，hash 变化，原节点再也定位不到，等于内存泄漏。
3. 预估容量。已知元素数量 n 时用 new HashMap<>((int)(n / 0.75f) + 1)，避免反复扩容。JDK 19 起可以用 HashMap.newHashMap(n)。
4. 遍历时删除用 Iterator.remove 或 removeIf，直接 map.remove 会触发 fail-fast。
5. computeIfAbsent 的映射函数里不要修改同一个 map，否则可能抛 ConcurrentModificationException 或死循环。
6. 不要依赖 HashMap 的遍历顺序，需要顺序用 LinkedHashMap，需要排序用 TreeMap。

八、小结

• HashMap 是数组桶 + 链表 + 红黑树，定位用 (n-1) & hash，要求容量为 2 的幂。
• hash 扰动把高 16 位异或到低位，提升低位离散度，减少冲突。
• put 采用尾插，链表长度达 8 且容量达 64 才树化，否则优先扩容。
• 扩容为 2 倍，利用 hash & oldCap 把链表拆成低位链和高位链，无需重算 hash。
• 16、0.75、8、64 这些数字都有源码注释或概率依据支撑，不是随意设定。
• HashMap 非线程安全，并发场景使用 ConcurrentHashMap 及其原子复合方法。