京公网安备11010502063487号"链表长度到 8 就转红黑树"是背得最熟的 HashMap 八股之一。做一个 hashCode 永远返回同一个值的坏类,真实反射进 HashMap 的内部 table,把这句话拆成三个可以验证的具体问题:到底是第几个触发的、容量不够会怎样、remove 之后会不会转回来。
上一篇:ThreadLocal 内存泄漏:线程池里不调用 remove(),真实测出 23MB 残留
正常的 key 分布均匀,几乎不可能自然凑出 8 个碰撞;所以自己写一个 hashCode 恒定的类,强行把碰撞做出来。
HashMap 的每个桶本来存的是一条单向链表,put 的时候如果发现某个桶里的节点数达到阈值,会尝试把这个桶从链表转成红黑树(TreeNode),用 O(log n) 的查找替换最坏情况下 O(n) 的链表遍历。要真实触发这个过程,先得让很多 key 真实落进同一个桶:
TreeifyDemo.java(实验用坏类) static final class BadHash { final int id; BadHash(int id) { this.id = id; } @Override public int hashCode() { return 42; } // 永远返回同一个值 }
HashMap 定位桶用的不是 hashCode() 原始值,而是先做一次扰动(h ^ (h >>> 16))再和 (table.length - 1) 做按位与。因为这个坏类的 hashCode() 永远是 42,扰动后的值也永远一样,所以不管插入多少个 BadHash 实例,它们都会真实落进同一个桶——用反射拿到 HashMap.table 字段,再拿到这个桶里节点的 getClass().getSimpleName(),就能真实看到它从 Node 变成 TreeNode 的那一刻。
预先把 HashMap 容量开到 128,排除"容量不够导致扩容而不是树化"这个变量,单独看节点数这一个维度。
put 第 1 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=1 put 第 2 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=2 put 第 3 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=3 put 第 4 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=4 put 第 5 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=5 put 第 6 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=6 put 第 7 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=7 put 第 8 个 -> table.length=128, 桶[42] 节点类=Node, 沿 next 链长=8 put 第 9 个 -> table.length=128, 桶[42] 节点类=TreeNode, 沿 next 链长=9
真实结果和背下来的"8 就转树"有个容易被忽略的偏差:桶里已经有 8 个 Node 的时候,类型仍然是链表;要等第 9 个节点插入完成,才真实看到类型变成 TreeNode。JDK 里这个阈值常量确实叫 TREEIFY_THRESHOLD = 8,但它的语义是"桶里已有节点数达到 8(不算新插入的这个)才触发树化检查",而不是"总节点数到 8 就树化"——真实数据里,总节点数是 9 的时候,树化才真正发生。
把"真实验证一"的 9 步插入串成动画:每一帧都是真实反射读出的桶内节点数和节点类型,没有手工画。
这次不预先给容量,用默认的 new HashMap<>() 从 16 开始,看看碰撞节点数早就过了 8 之后,到底发生了什么。
put 第 1 个 -> table.length= 16, 桶[10] 节点类=Node put 第 2 个 -> table.length= 16, 桶[10] 节点类=Node put 第 3 个 -> table.length= 16, 桶[10] 节点类=Node put 第 4 个 -> table.length= 16, 桶[10] 节点类=Node put 第 5 个 -> table.length= 16, 桶[10] 节点类=Node put 第 6 个 -> table.length= 16, 桶[10] 节点类=Node put 第 7 个 -> table.length= 16, 桶[10] 节点类=Node put 第 8 个 -> table.length= 16, 桶[10] 节点类=Node put 第 9 个 -> table.length= 32, 桶[10] 节点类=Node put 第 10 个 -> table.length= 64, 桶[42] 节点类=Node put 第 11 个 -> table.length= 64, 桶[42] 节点类=TreeNode put 第 12 个 -> table.length= 64, 桶[42] 节点类=TreeNode第 9 个插入本该按上面的实验触发树化,但因为此时 table.length 只有 16,真实观察到的是扩容(16→32),不是树化;紧接着第 10 个插入又连续触发了一次扩容(32→64),同一个桶里的节点类型全程停留在 Node,直到容量真正达到 64、第 11 个插入完成后,才第一次真实看到 TreeNode
JDK 源码里这个门槛叫 MIN_TREEIFY_CAPACITY = 64:即使某个桶的节点数已经达到树化检查的阈值,只要整个 table 的容量还没到 64,treeifyBin 方法内部会选择直接扩容而不是真的转成树,理由很直接——容量太小时桶本来就容易碰撞,先扩容通常就能把这一堆节点重新打散到不同的桶里,用不着红黑树。真实数据里能看到这个决策的连锁反应:一次该树化的时机被容量门槛拦下来,直接引发了两次连续扩容。
另一句常见说法是"节点数减到 6 就转回链表",拿真实数据核对一下这句话在 remove() 场景下成不成立。
接上第一组实验(容量 128,已树化,桶里 10 个节点),从 10 个开始逐个 remove,每一步都反射检查桶里节点的类型:
remove 到剩 9 个 -> 桶[42] 节点类=TreeNode remove 到剩 7 个 -> 桶[42] 节点类=TreeNode remove 到剩 5 个 -> 桶[42] 节点类=TreeNode remove 到剩 4 个 -> 桶[42] 节点类=TreeNode remove 到剩 3 个 -> 桶[42] 节点类=TreeNode remove 到剩 2 个 -> 桶[42] 节点类=TreeNode remove 到剩 1 个 -> 桶[42] 节点类=TreeNode remove 到剩 0 个 -> 桶[42] 节点类=TreeNode一路删到只剩 1 个节点,类型全程真实保持 TreeNode,没有在剩 6 个、剩 5 个或任何中间点观察到转回 Node 的情况