HashMap 内部机制与 JDK7→JDK8 演进

TL;DR（30 秒扫完）

• put 四步：①hash(key)=h^(h>>>16) 高位异或；②(n-1)&hash 定位桶；③空桶直放/非空遍历 equals 覆盖或尾插；④链长>8 且容量≥64 转树，size>threshold 扩容
• resize 位运算：e.hash & oldCap 判断——0 留原位，非 0 搬到 index+oldCap
• JDK7→8 七改动：头插→尾插、引入红黑树、hash 算法改造、resize 位运算、TreeNode 拆分、转树双门槛、新增函数式 API
• 并发问题六类：size 错乱、put 覆盖、get null、迭代 CME、check-then-act、可见性缺失
• 替代首选：ConcurrentHashMap（详见 hash-map-concurrent.md）

关键结论

完整讲解（费曼四步）

STEP 1 · 概念

STEP 2 · 大白话

类比：HashMap 就像一个多层储物柜。最外层是"柜号"数组（桶），每个柜子里挂着"袋子"（链表），袋子里有多个"钥匙-物品对"。取东西时先按 key 的 hash 值定位到哪个柜号（桶），再从柜子的袋子里翻钥匙找物品。如果某个柜子挂的袋子太长（哈希冲突严重），就把袋子升级成"书架"（红黑树），查找更快。

JDK8 的改进：原来 JDK7 的柜子挂新袋子时用"头插法"（新袋子插到最前面），但两个工人同时扩容时会把链表搅成环——现在改成了"尾插法"（新袋子挂到最后），避免环形；扩容时用位运算判断袋子该留原位还是搬到柜子右边（index+oldCap），不用重新算 hash。

STEP 3 · 底层

put 完整流程（JDK8）

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

// 核心逻辑
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // ① 空表初始化（容量取 initialCapacity 的 2 的幂）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // ② 桶定位：(n-1) & hash，因为容量是 2 的幂，等价于取模
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);   // 空桶：新建 Node 直接放
    
    else {
        // ③ 桶非空：遍历
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;                                  // 头节点命中：覆盖 value
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, 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);                   // 且容量 ≥ 64 才转树
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;                                    // 遍历中命中：准备覆盖
            }
        }
        if (e != null) {   // 命中覆盖
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)         // ④ 扩容检查
        resize();
    afterNodeInsertion(evict);
    return null;
}

get 完整流程

public V get(Object key) {
    return getNode(hash(key), key);
}

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);  // ② 树形查找 O(log n)
            while ((e = e.next) != null) {              // ③ 链表遍历
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            }
        }
    }
    return null;                                      // ④ 未命中
}

hash 算法（JDK8）

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

• 容量 n 是 2 的幂时，n-1 的二进制是低 n 位全 1（如 16 = 10000, 15 = 01111）
• & 01111 等价于"取低 4 位"，也等价于 hash % 16
• 但按位与比取模运算快得多

• equals 相等 → hashCode 必相等（正契约）
• hashCode 相等 → equals 不一定相等（哈希冲突，反契约）
• 打破后果：put 时 A/B 的 hash 不同，equals 无法触发覆盖 → 两个 equals 相等的 key 各占一个桶；get 时可能找不到刚 put 的值

resize 扩容（JDK8）

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) {
        newCap = (oldThr > 0) ? oldThr : DEFAULT_INITIAL_CAPACITY;  // 16
        newThr = (int)(newCap * DEFAULT_LOAD_FACTOR);               // 12
    }
    // ② 达 MAX_CAP 不再扩容量，只增 threshold
    else if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    // ③ 常规扩容：容量翻倍
    else if ((newCap = oldCap << 1) > MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else {
        newThr = oldThr << 1;
    }
    
    @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 = oldTab[j];
            if (e == null) continue;
            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);  // 树桶：拆分，size<6 退化
            }
            else {
                // 关键：链表按 e.hash & oldCap 拆成"原位"和"远端"两串
                Node<K,V> loHead = null, loTail = null;  // e.hash & oldCap == 0 的
                Node<K,V> hiHead = null, hiTail = null;  // e.hash & oldCap != 0 的
                do {
                    if ((e.hash & oldCap) == 0) {
                        loTail = (loTail == null) ? loHead = e : loTail.next = e;
                    } else {
                        hiTail = (hiTail == null) ? hiHead = e : hiTail.next = e;
                    }
                } while ((e = e.next) != null);
                
                if (loHead != null) newTab[j] = loHead;                          // 原位
                if (hiHead != null) newTab[j + oldCap] = hiHead;                 // 远端 index+oldCap
            }
        }
    }
    threshold = newThr;
    return table;
}

• 容量从 oldCap 变成 newCap=oldCap×2，newCap-1 比 oldCap-1 多了一位 1（高位）
• 原 index = hash & (oldCap-1)，只用了低 n 位
• 新 index = hash & (newCap-1)，多了第 n 位
• 所以新旧 index 差在第 n 位：
• e.hash & oldCap == 0（第 n 位为 0）→ 新 index = 旧 index（原位）
• e.hash & oldCap != 0（第 n 位为 1）→ 新 index = 旧 index + oldCap（远端）
• 性能收益：不用重新 hash，只判断一个 bit

JDK7 vs JDK8 演进对比

转树与退化的双门槛

并发问题六大分类

替代方案对比

• 默认用 ConcurrentHashMap
• 复合操作（如"不存在则创建"）用 computeIfAbsent 保证原子
• 不可变场景用 unmodifiableMap
• 共享计数器用 LongAdder/AtomicLong，不要用 Map 存计数

STEP 4 · 简化

一句话总结：HashMap 是"数组+链表+红黑树"三层结构，JDK8 用 hash 高位异或 + 尾插法 + resize 位运算 + 链长>8 转树 四大优化解决查找、扩容、并发三个痛点，但并发正确性仍需 ConcurrentHashMap。

延伸追问

速查表

数据结构：数组 + 链表 + 红黑树（JDK8+）

put 四步：
  ① hash(key) = key.hashCode() ^ (key.hashCode() >>> 16)
  ② index = (n - 1) & hash
  ③ 桶空 → 直放；桶非空 → 遍历 equals 覆盖或尾插
  ④ 链长>8 且容量≥64 转树；size>threshold 扩容

resize 五步（JDK8）：
  ① 首次：newCap=16，threshold=12
  ② 常规：newCap=oldCap<<1，threshold=oldThr<<1
  ③ 达 MAX_CAP(1<<30)：只增 threshold
  ④ 遍历旧桶，按 e.hash & oldCap 拆两串
  ⑤ 树桶 split，size<6 退化回链表

JDK7→JDK8 七改动：
  头插→尾插 / 引入红黑树 / hash 位运算 / resize 位运算 /
  TreeNode 拆分 / 转树双门槛 / 新增函数式 API

并发问题六类：
  size 错乱 / put 覆盖 / get null / 迭代 CME / check-then-act / 可见性缺失

替代方案：ConcurrentHashMap 首选

关键常量：
  TREEIFY_THRESHOLD=8, UNTREEIFY_THRESHOLD=6, MIN_TREEIFY_CAPACITY=64
  DEFAULT_INITIAL_CAPACITY=16, DEFAULT_LOAD_FACTOR=0.75

关联题目

• [ ] 《HashMap在get和put时经过哪些步骤？》— 2026-10-09 Round 1 Q4, ⭐⭐⭐（漏 hash 位运算、get 树形分支）
• [ ] 《HashMap是如何扩容的？》— 2026-10-09 Round 1 Q5, ⭐⭐（只答触发条件，无扩容过程）
• [ ] 《JDK1.8中HashMap有哪些改变？》— 2026-10-09 Round 1 Q6, ⭐⭐⭐（漏 hash 算法、Node 拆分、树退化）
• [ ] 《HashMap用在并发场景中有什么问题？》— 2026-10-09 Round 1 Q7, ⭐⭐⭐（漏 get 中间态、CME、check-then-act）
• [ ] 《HashMap、Hashtable和ConcurrentHashMap的区别？》— 2026-10-09 Round 1 Q2, ⭐⭐⭐（主线对，广度不足）

关联知识

• ConcurrentHashMap 并发机制与 synchronized 决策
• 红黑树原理与 5 条性质
• String 的三大设计模式