企业官网建设流程全解析

很多人背面试题，问“JDK 1.8 的 HashMap 改了什么”，张口就是红黑树。但说实话，红黑树只是这次升级里最显眼的一块补丁，真正让 HashMap 从 JDK 1.7 脱胎换骨的，是 hash 计算、扩容迁移、插入策略、初始化时机、树化阈值、新增 API 这一整套联动的改动。这篇文章就照着源码把 1.8 的 HashMap 逐层拆开，看看除了红黑树，它到底还改了什么、为什么这么改，以及这些改动在日常开发和线上排查里意味着什么。适合正在准备面试、或者想真正读懂 HashMap 源码的 Java 开发。

1. 一图看懂 1.8 的 HashMap：绝不只是多了棵红黑树

1.1 一次升级，改的是整套存取逻辑

JDK 1.7 的 HashMap 内部结构是“数组 + 单向链表”，1.8 的核心结构变成“数组 + 单向链表 + 红黑树”。但这只是表象，真正要理解这次升级，得看整条存取链路。

第一，hash 函数从多次扰动变成一次高低位异或，目的是在保证分布质量的前提下降低计算成本；第二，插入新节点从头插法改成尾插法，直接解决了并发扩容时链表成环的问题；第三，扩容迁移不再对每个元素重新计算下标，而是通过e.hash & oldCap把链表拆成“高位”和“低位”两条，原地搬家；第四，数组不再在构造时初始化，而是第一次 put 时才创建，顺便省下空数组的内存占用；第五，删除或扩容后可能触发红黑树退回链表，防止性能反而退化；第六，Map 接口在 JDK 8 新增的一批默认方法，HashMap 全部实现或覆盖，比如 putIfAbsent、computeIfAbsent、merge。

这些改动不是孤立的，它们互相配合。比如树化阈值 8 和“数组长度至少 64”绑定在一起，是因为在小数组上直接树化不如扩容划算；又比如扩容时的高低位移位是靠“容量永远是 2 的幂”来保证的，而容量是 2 的幂又是因为 hash 取模用(n - 1) & hash来提速。这套逻辑链才是这次升级的真正精华。

1.2 1.7 的问题集中在哪，决定了 1.8 怎么改

把 1.7 的痛点列出来，就明白 1.8 为什么这么改。

1.7 的 hash 函数使用了四次位运算扰动，代码是这样的：

h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);

这样做确实让分布更均匀，但每次 put、get、remove 都要跑一遍，在高频访问场景下是纯开销。尤其当 key 的 hashCode 质量本身已经很稳定时，重复扰动带来的增益有限，浪费却很实在。

1.7 扩容时的迁移逻辑是典型的头插法：

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while (null != e) { Entry<K,V> next = e.next; int index = indexFor(e.hash, newCapacity); e.next = newTable[index]; newTable[index] = e; e = next; } } }

每次把链表往前插，导致迁移后链表逆序。单线程没问题，多线程并发扩容时，两个线程可能对同一个链表不断互插，最终出现e.next = e的环状引用。这个问题当年在 Java 社区讨论得非常热烈，也是 1.8 必须修改的动因之一。

还有一点：1.7 构造 HashMap 时就直接创建数组，table = new Entry[capacity]。哪怕你 new 完压根不用，这段内存也占着。对于长期存活但很少使用的对象，这是实打实的浪费。

1.3 从构造期初始化到懒加载，threshold 语义改变了

1.8 的构造方法基本不干活，只记录容量和负载因子，真正分配数组发生在第一次 put 时。这一点看源码很直观：

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) { // 扩容逻辑 } else if (oldThr > 0) { // 初始化：构造时指定的容量就存在 threshold 里 newCap = oldThr; } else { // 无参构造，用默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 后续还有对新 threshold 的计算 }

这里有个容易被忽略的细节：JDK 8 无参构造创建出来的 HashMap，内部 table 是 null，threshold 是 0，什么都没分配。只有当第一次 put 时才会走 resize() 完成初始化。对于“new 出来但没怎么用”的场景，能省下那块 Node[] 内存。同时，因为你传入的 initialCapacity 会先经过 tableSizeFor 处理成 2 的幂，再存到 threshold 里，所以初始化容量和 threshold 的语义在 1.8 里是有重叠的——这一点源码注释里明确说了，读的时候别懵。

顺带提一句，tableSizeFor 是 JDK 8 里一个经典的位运算技巧：

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

通过不断把最高位的 1 向右传播，最终得到大于等于 cap 的最小 2 的幂。这也是整个 HashMap 能建立在“容量为 2 的幂”这一前提上的根基。

2. hash() 越改越简单，背后的数学逻辑是什么

2.1 从四次扰动到一次异或

1.8 的 hash 函数精简到了让人怀疑的程度：

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

连 static 修饰符都从 1.7 的成员方法变成了静态方法，说明调用方（putVal、getNode 等）保证传入非 null，这里对 null 只是顺手兜底。

这一眼看上去就是“高 16 位异或低 16 位”，把 hashCode 的高位信息搅拌到低位里。为什么这个操作够用？因为 HashMap 计算桶下标用的是(n - 1) & hash，其中 n 是数组长度，永远是 2 的幂，n - 1 的二进制就是一连串低位的 1。如果数组长度是 16，n - 1 只有低 4 位是 1，那么无论 hashCode 高位多丰富，最终参与下标计算的只有低 4 位。如果不做任何处理，两个不同 key 只要低 4 位相同就会进同一个桶，哪怕它们的高 16 位差异巨大。

2.2 为什么一次 h >>> 16 就够了

有个知识点容易被忽略：String、Integer 这些常见 key 的 hashCode 实现质量本来就稳定，而且 Java 7 起 String 会缓存 hash 值，重复取用成本很低。既然源头散列质量上来了，HashMap 这边就不需要像 1.7 那样用四次位运算去反复折腾，一次高低位混合足够把分布拉开，还能把每次存取里浪费在扰动上的 CPU 周期省掉。

我们可以算一笔账：假设两个 key 的 hashCode 分别是 0x12345678 和 0xABCDEF78，数组容量 16。只看低 4 位，两个 hash 的低 4 位都是 8，必然冲突。但经过h >>> 16异或后，0x1234 ^ 0x5678 = 0x444C，低位变成 0xC；0xABCD ^ 0xEF78 = 0x44B5，低位变成 0x5。冲突就这么被解开了一部分。虽然这个例子稍显理想化，但思路是对的：让高位参与低位，是花费最小代价、换取分布质量的方案。

2.3 分布质量变差时，树化只是兜底而不是设计常态

很多人在解释红黑树时说“为了让 HashMap 查询更快”，这个说法不够准确。更准确的说法是：在 hash 分布理想的情况下，每个桶里的链表长度接近 0 或 1，根本轮不到红黑树出场。红黑树是给“极端不均匀”情况准备的兜底方案。一旦你看到生产环境里某个 HashMap 真的树化了，第一反应应该是去查 key 的 hashCode 是否合理，而不是庆幸它引入了红黑树。

正因为如此，树化成本才被设计得很谨慎：TreeNode 大约是普通节点的两倍大小，树化后左旋右旋、变色等维护成本也不低。JDK 才把树化阈值设为 8，且要求数组长度至少 64，目的就是把“树化”限定在真正的病态场景里，而不是让它成为一种常见状态。

3. 尾插法与扩容优化：并发时代最重要的两个“隐形改动”

3.1 头插法改尾插法，死循环是怎么没的

1.8 的 putVal 在遍历链表时，会用尾插法把新节点接在链表末尾。对照 1.7 每次插到头部，这个改动看似平平无奇，实际解决了一个困扰多年的并发死循环问题。

1.7 死循环的原因，前面已经概述过，这里展开讲一下现场。线程 A 和线程 B 同时触发扩容，两个线程都会走 transfer 迁移同一个桶里的链表。假设原链表 a -> b -> c，线程 A 执行到一半，把 a 放到新桶并准备处理 b 时被切走；线程 B 完整执行完迁移，新链表顺序变成 c -> b -> a。这时线程 A 恢复，它手里还攥着指向 b 的引用，继续把 b 头插到新桶，紧接着又处理 a，结果 a.next 指向 b，b.next 也指向 a，形成环。后续任何 get 落到这个桶，都会在链表里转圈，CPU 直接打满。这个问题在当年的大型 Java 应用里是真实踩过的坑。

1.8 的扩容逻辑改用尾插，并且两个子链表各自维护 loHead/loTail 和 hiHead/hiTail，迁移后顺序保持原样，链表本身不会再反转，因此“两个线程互插形成环”的路径被切断了。当然必须强调：这并不代表 HashMap 线程安全。并发写仍然会有数据覆盖、size 计数错误等问题，只是死循环这一颗最刺眼的雷被拆掉了。需要线程安全，老老实实用 ConcurrentHashMap。

3.2 扩容不再重新计算下标：高低位链表分裂

1.8 的 resize() 里有一段很经典的代码，在遍历每个桶时，用(e.hash & oldCap)判断元素归属：

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 { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } e = next; } while (e != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }

理解这段代码，关键在于容量是 2 的幂这个前提。扩容前容量 oldCap 是 2^k，下标计算是hash & (oldCap - 1)。扩容后容量变成 2 * oldCap 也就是 2^(k+1)，下标计算变成hash & (2*oldCap - 1)。对比两个掩码，扩容后只在原来基础上多了一个 bit：oldCap 那一位。这一位是 0 还是 1，直接决定了元素留在原位置还是搬到“原位置 + oldCap”。

所以(e.hash & oldCap)就是判断扩容新增的那一位。等于 0 的留在原下标 j；等于 1 的搬到 j + oldCap。这个判断只需要一次位与运算，比 1.7 里每次重新计算 index 再头插快得多，也避免了大量 hash 重算的开销。1.7 迁移时要遍历所有元素重新算下标；1.8 迁移对每个元素只有一次位与运算加一次移动，性能提升在元素量大、扩容频繁时非常明显。

3.3 并发场景下：没有死循环不等于线程安全

我在网上见过不少说法：“JDK 1.8 的 HashMap 并发是安全的，因为用尾插法解决了死循环。”这是典型的以偏概全。并发环境下 1.8 的 HashMap 依然有这些问题：

第一，两个线程同时 put 不同 key 落到同一个空桶，都判断桶为空，各自把节点放进去，后写的覆盖先写的；第二，两个线程同时 put 相同 key，一个赋值成功，另一个丢更新；第三，size 计数不是原子的，modCount、size 存在丢计数；第四，并发 resize 时，两个线程看到的旧链表状态可能不一致，迁移后仍可能丢数据或产生不可预期的结构。

判断标准很简单：任何多线程环境，HashMap 都不能直接裸用。1.8 只是把“死循环”这种灾难性问题缓解了，但丢失数据、覆盖更新的频率并不低。我在线上系统里见过很多并发 HashMap 出问题的案例，最后排查下来全是该用 ConcurrentHashMap 的地方用了 HashMap。

4. 红黑树的原理，以及为什么叫“树化兜底”

4.1 从链表到红黑树：性能模型变化

链表查找是 O(n)，红黑树查找是 O(log n)。如果某个桶里塞了 100 个元素，链表查找最差要比较 100 次，红黑树只要比较约 7 次。当 hashCode 质量很差，或者容量设置不合理导致大量 key 挤进少数桶时，链表会变成性能瓶颈，树化就是在这时候兜底的。

为什么选红黑树而不是 AVL 树，这个问题很经典。AVL 树是严格平衡的，每个节点左右子树高度差不超过 1，查找确实更快，但代价是插入和删除时为了维持严格平衡，可能触发非常频繁的旋转操作。红黑树的平衡是近似平衡，它允许一定程度的“不完美”，换来的却是插入删除时旋转次数显著更少。HashMap 是读写都高频的数据结构，碰撞严重时每一秒可能都有大量插入删除，选红黑树的工程权衡比 AVL 更合理。红黑树维护的五个性质保证的是“从根到叶子的所有路径中，最长路径不超过最短路径的 2 倍”，这足以把查找复杂度控制在 O(log n)。

4.2 红黑树的五大性质

红黑树在普通二叉搜索树基础上，给每个节点加了一个颜色属性，并通过下面五条性质维持平衡：

1. 每个节点要么是红色，要么是黑色；
2. 根节点是黑色；
3. 所有叶子节点（NIL 空节点）是黑色；
4. 红色节点的两个子节点必须是黑色，也就是说从任意节点到叶子，不能出现连续两个红色节点；
5. 从任一节点到它的每个叶子节点，所有路径包含相同数目的黑色节点。

第 4 和第 5 条是核心。第 4 条限制了红色节点不能连坐，第 5 条保证了任意路径上黑色节点数量一致，两者合起来推出“最长路径是红黑交替，最多是最短（全黑）路径的两倍”，这就是红黑树近似平衡的数学根基。

TreeNode 的结构上，HashMap 不仅记录了 parent、left、right，还额外保留了 prev 指针：

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

prev 的存在是为了在树化、split、remove 时能方便地把树节点链回链表，因为 HashMap 里树节点和链表节点需要经常互相转换。

4.3 插入修复与删除修复要点

先说插入。新节点一律先涂成红色，因为这样不会破坏第 5 条（黑色节点数量不变），只需要处理可能出现的“连续红色”问题。如果父节点是黑色，直接插入，什么也不用做。如果父节点是红色，就要根据叔叔节点（父节点的兄弟）的颜色分两类处理。

叔叔是红色：把父节点变黑、叔叔节点变黑、祖父节点变红，然后以祖父节点为当前节点继续向上检查，相当于把红色“上移”了一层。

叔叔是黑色：这种情况父红、叔叔黑，当前节点是红，违反第 4 条，但可以通过旋转修复。旋转分四种情况，对应 LL、LR、RL、RR。LL 和 RR 是一次单旋转能解决的，LR 和 RL 需要先对父节点做一次旋转，调整成 LL/RR 形态，再做单旋转。旋转的同时要记得变色：一般旋转后，新的子树根变成黑色，它的两个子节点变成红色。

删除比插入复杂得多。删除一个红色节点，直接删掉不影响黑高；删除黑色节点会导致某条路径上黑色节点少一个，破坏第 5 条，所以需要视兄弟节点的颜色和侄子节点的颜色做多轮调整。大方向是：兄弟是红色时，先通过一次旋转把兄弟变为黑色，把问题下放；兄弟是黑色时，看它的孩子的情况，两个侄子都是黑色就借位变色，把矛盾向上转移；有一个侄子为红，就通过旋转和变色重新达到平衡。实际编码时 TreeNode.removeTreeNode 里还同时做链表退化的判断：如果树节点太少，就把它转换回普通链表。

红黑树这套规则面试里常说常考，但绝大多数业务开发不一定需要手写。真正要理解的是最终结论：红黑树能让最坏情况下的操作变成 O(log n)，并且删除修复虽然分支多，但均摊下来旋转次数有限，工程上可接受。

4.4 8、6、64 三个阈值是拍脑门定的吗

这三个数字都不是随便写的。

TREEIFY_THRESHOLD = 8，依据是泊松分布。JDK 官方注释里给出过一张表，假设哈希函数是理想随机分布，桶内元素数量 k 的概率 P(k) = (e^-λ · λ^k) / k!，取平均每个桶的元素数 λ = 0.5，那么 k = 8 时的概率大约是 0.00000006，也就是千万分之六。链表长度超过 8 的概率低到几乎不可能在正常数据里出现。所以一旦真的出现，基本可以断定 hashCode 分布很差或者说容量不合适，这时候树化才划算。

UNTREEIFY_THRESHOLD = 6 是树退化为链表的阈值，它和 8 之间留了两格缓冲。如果退化阈值也设为 8，那么一个桶的元素数在 7、8 之间抖动时，会反复在“链表 -> 树 -> 链表”之间切换，每次转换都有开销。设置成 6，从 8 减到 6 需要删除或搬走不少元素，触发概率低，能有效避免这种振荡。

MIN_TREEIFY_CAPACITY = 64 的意义在于：如果数组长度还不到 64，哪怕某个桶链表长度到了 8，也不要急着树化，先扩容。因为数组小的时候，大量 key 挤到同一个桶，很可能是容量不足导致的，扩容能把元素分散到更多桶里，让冲突自然缓解。直接树化只是治标，扩容才是治本。源码里 treeifyBin 第一步就是这个判断。

4.5 扩容时红黑树的 split：树和链表互相转换

resize 里专门有一段处理 TreeNode 的代码，叫 split。它的逻辑和普通链表的高低分裂流程类似，但额外要考虑红黑树结构：把树上的节点按(e.hash & oldCap)拆成 lo 和 hi 两份，然后根据拆分后的数量决定保留树还是退化成链表。

final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) { TreeNode<K,V> b = this; TreeNode<K,V> loHead = null, loTail = null; TreeNode<K,V> hiHead = null, hiTail = null; int lc = 0, hc = 0; // 遍历双向链表形态的树节点，按 bit 拆两份 // ... if (loHead != null) { if (lc <= UNTREEIFY_THRESHOLD) tab[index] = loHead.untreeify(map); else { tab[index] = loHead; if (hiHead != null) loHead.treeify(tab); } } // hi 分支同理 }

没看代码前容易以为“扩容后红黑树还是红黑树”。实际上扩容会把整棵树拆开，如果某一边拆完只剩下 5、6 个节点，就没必要维持树结构了，直接 untreeify 成链表，避免树节点两倍内存的浪费。反过来，如果拆分后两边都还够大，会基于现有节点重新 treeify。所以树的形态在扩容过程中是动态变化的，不是钉死的。

5. 新增 API：日常开发被低估的效率提升

5.1 putIfAbsent、compute、merge 的语义与场景

JDK 8 的 Map 接口新增了一堆 default 方法，HashMap 基本都实现了。这些 API 对日常开发的帮助很大，尤其是缓存和统计场景。

putIfAbsent 是“没有才放”，返回值是旧值，如果之前没有则返回 null，语义直接。

computeIfAbsent 是高频场景里的神器。最常见的用法就是“取不到就初始化一个再放进去”：

Map<String, List<String>> userTags = new HashMap<>(); userTags.computeIfAbsent("u1001", k -> new ArrayList<>()).add("vip");

不用 computeIfAbsent 时，你得写三段：get、判空、put。关键是这三段不是原子的，并发下两个线程可能各自 new 两个 ArrayList，其中一个白白丢掉。computeIfAbsent 把“不存在则初始化”这个过程收进了 Map 内部，写起来简洁，语义上也更接近期望。

computeIfPresent 针对“key 存在才对 value 做变换”的场景，比如更新计数器：

map.computeIfPresent("count", (k, old) -> old + 1);

merge 很适合聚合类逻辑，比如统计单词出现次数：

Map<String, Integer> freq = new HashMap<>(); for (String word : words) { freq.merge(word, 1, Integer::sum); }

这三个方法加上 getOrDefault、forEach、replaceAll，基本覆盖了日常读改写的大多数场景，能少写很多手写的判空和 put 逻辑。

5.2 使用这些 API 的常见坑

第一个坑：在 mappingFunction 里修改同一个 Map。computeIfAbsent 要求函数内不能对当前 Map 做结构性修改，否则可能抛 ConcurrentModificationException，有些场景甚至可能递归调用自身造成栈溢出。比如在 compute 里再调 compute，看起来合理，实际非常危险。

第二个坑：mappingFunction 返回 null 时，computeIfAbsent 不会往 Map 里放任何东西，这一点很多人预期不一致。

第三个坑：merge 的 remappingFunction 如果返回 null，会删除这个 key，而不是保留 null 值。这是相当隐蔽的行为，处理聚合结果时要尤其注意。

第四个坑：这些方法在 ConcurrentHashMap 上也有对应实现，但语义细节有差异，尤其是 compute 系列对并发和原子性的保证。如果需要并发环境下原子地“取-算-放”，直接用 ConcurrentHashMap 的 compute 系列，别在 HashMap 上先 get 再 put、然后自己加锁。

6. 常见问题与实战排查速查表

6.1 面试与使用中绕不开的经典问题

6.2 线上排查 HashMap 相关问题的经验

我在实际项目里遇到过几次和 HashMap 相关的诡异问题，印象很深。

一次是某服务在启动预热阶段一次性灌入大量数据，HashMap 频繁扩容，CPU 飙升。排查后发现构造时没指定容量，默认 16 一路扩上去。后来改成按预估容量计算后的值（expectedSize / 0.75f + 1）一下子就稳了。所以凡是知道大概数据量的场景，一定要用带容量参数的构造器。

另一次是某个统计接口突然慢了一个数量级，看火焰图发现某个 HashMap 的桶里链表特别长，再看 key 的 hashCode，原来是某个业务对象重写了 hashCode，但实现非常粗糙，大量对象落到同一个桶。红黑树虽然兜了底，但树化后的 TreeNode 又大又慢，根本原因还是散列质量差。把 hashCode 改好后性能恢复正常。

还有一次是自定义对象当 key，但对象是可变的，某个字段被改后 hashCode 跟着变，导致在 HashMap 里再也 get 不到原来的值，数据像是“丢”了。后来检查到这个问题后用不可变对象做 key 才解决。

这三类问题其实都指向同一个原则：理解 HashMap 的性能模型，核心是理解 hash 分布。红黑树只是最后一道保险，不能把它当成性能问题的解药。

如果让我总结最值得记住的一条经验，那就是：别把红黑树当成 HashMap 的全部。真正的高性能哈希表，依赖的是优质的散列分布、合理的容量规划和克制的数据结构转换。红黑树只是一个装在最外层的保险丝，正常工作状态下你根本感觉不到它存在；一旦你感受到它，往往意味着前面的 hash 和容量环节出了问题。这也是我在排查线上性能问题后最深的体会：与其盯着树化代码，不如回过头检查 key 的 hashCode、初始容量和并发使用场景，这三处才是决定 HashMap 命运的地方。