为什么不直接使用红黑树紧接上一篇我们知道了 JDK 8 为什么要在链表过长时引入红黑树但随之而来的问题是既然红黑树的查询效率O(log N)明显高于链表的O(N)那为什么不干脆在第一次发生哈希冲突的时候就直接使用红黑树而是先试用链表非要等到链表长度达到8这么长了才开始转为红黑树呢这主要是因为在底层设计的时候对内存占用和执行效率很抓狂不在一开始就使用红黑树核心原因有三点空间占用翻倍红黑树的节点大约比普通链表节点大了一倍。小数据量下链表比数组块当数据只有几个的时候红黑树需要维持平衡左旋右旋、变色这些复杂运算还是比较耗时间的。而链表只需要一个for循环无脑遍历在CPU缓存的加持下几下子就走完了比树还快一点。概率论的防线树化本质上是应对黑客攻击或者劣质Hash算法的防御机制正常情况下不该发生。在源码中JDK作者为我们留下了一段注释利用了泊松分布// 【源码注释 A空间权衡】 // TreeNodes are about twice the size of regular nodes... // 翻译树节点TreeNode的体积大约是普通节点Node的两倍... // 【源码注释 B泊松分布概率表】 // 理想情况下在随机 Hash 码下哈希桶节点的分布遵循泊松分布Poisson distribution // 0: 0.60653066 // 1: 0.30326533 // 2: 0.07581633 // 3: 0.01263606 // ... // 7: 0.00000094 // 8: 0.00000006 -- 注意这个概率先一个一个来看。点首先是内存占用问题。开源码的TreeNode会发现它除了继承普通的Node还多出来parent、left、right、prev四个指针以及一个boolean red颜色属性。如果一开始就使用树的话内存会飙升非常浪费内存。也就是说你可以按照下面的路径去找java.util.HashMap ├── static class NodeK,V // 普通链表节点 └── static final class TreeNodeK,V extends LinkedHashMap.EntryK,V然后把Node和TreeNode放在一起对比。① 普通节点 Nodestatic class NodeK,V implements Map.EntryK,V { final int hash; final K key; V value; NodeK,V next; }可以看到一个普通节点只有四个成员hash key value next画出来就是┌──────────┐ │ hash │ │ key │ │ value │ │ next ───────► └──────────┘就是一个最普通的单链表节点。② TreeNode继续往下翻源码会看到static final class TreeNodeK,V extends LinkedHashMap.EntryK,V { TreeNodeK,V parent; TreeNodeK,V left; TreeNodeK,V right; TreeNodeK,V prev; boolean red; }如果展开来看它实际上拥有的成员更多。因为它继承的是LinkedHashMap.Entry而LinkedHashMap.Entry又继承HashMap.Node所以 TreeNode 实际拥有hash key value next before after parent left right prev red其中真正为了红黑树增加的是parent left right prev red③ 为什么说体积大约翻倍JDK 作者在源码注释里写的是TreeNodes are about twice the size of regular nodes.注意他说的是about twice也就是大约两倍并不是精确两倍。为什么因为 JVM 对象大小不仅仅由成员变量决定还有对象头对齐填充Padding是否开启压缩指针Compressed Oops32 位还是 64 位 JVM所以不同 JVM 上Node ≈ 32B TreeNode ≈ 56B~64B因此JDK作者没有说exactly twice而是about twice这是非常严谨的表述。然后就是看概率JDK作者经过严密的数学计算得出只要Hash算法正常一个格子里面发生冲突并且挂上8个节点的概率是千万分之六(0.00000006)。也就是说在千万分之六的极端概率才会发生的事情根本没有必要在一开始就让所有节点失去承担体积翻倍以及旋转变色的代价。阈值定为8纯粹是为了在遭遇极端哈希冲突(比如故意发一堆Hash值相同的请求试图瘫痪服务器)时保住系统不崩溃的一道防线。关于泊松分布可以看一下这个链接泊松分布和指数分布10分钟教程 - 阮一峰的网络日志两个例子链表找几个元素就像街边的夫妻便利店。店里总共就 5 行货架长度 5 的链表。你要找一瓶酱油扫一眼就找到了。如果你非要在这个小店里引入一套极其复杂的“沃尔玛级数字仓储定位系统红黑树”每天光是录入系统、维护系统花的时间比你直接找东西的时间还长纯属吃力不讨好。红黑树防极端情况但如果某一天你的店被人恶意塞进了一万件商品千万分之一的概率堆得连下脚的地方都没有了你这辈子都找不到那瓶酱油了。这时候“沃尔玛仓储系统树化”就必须被激活否则你的店就瘫痪了。这里画一个简略性能图耗时 (时间复杂度常数影响) │ │ 红黑树 (初始化和维持平衡耗时但后期平缓) │ / │ / │ / 链表 (开始极快但数据大了线性飙升) │ ---------- /---------/-------- │ / / │ / / │ / / │ / / │ / / │ / / └───────────────────────────────► 节点数量 N ▲ 大概在 8 附近链表的劣势开始大于树的劣势此时切换性价比最高。为什么树化阈值为8既然触发树化的阈值TREEIFY_THRESHOLD 8上篇讲解过那么我们逆向思维一下当调用map.remove(key)删除数据或者map在扩容时数据被打散导致红黑树上的节点越来越少的时候为了节省内存它势必会退化成普通的链表。源码中有写退化的阈值是多少static final int UNTREEIFY_THRESHOLD 6;现在问题又来了为什么退化成链表的阈值是6而不是7呢明明到8才能变成树为什么不是减到7就立马变回链表非要在中间空出一个7// 【源码常量】 // 树化阈值达到 8 变树 static final int TREEIFY_THRESHOLD 8; // 退化阈值降到 6 变回链表 static final int UNTREEIFY_THRESHOLD 6;关于这个问题我自己写了一段测试分别将阈值设置为6和7/** * 模拟 HashMap 中桶内节点在链表与红黑树之间的转换 * 对比退化阈值为 6 和 7 时的震荡频率。 */ public class ThrashingSimulation { private static final int TREEIFY_THRESHOLD 8; // 树化阈值固定 private static int UNTREEIFY_THRESHOLD; // 退化阈值可调 private static int size; // 当前桶内节点数 private static boolean isTree; // 当前是否处于树结构 private static int treeifyCount; // 树化触发次数 private static int untreeifyCount; // 退化触发次数 public static void main(String[] args) { // 分别测试两个阈值6JDK实际值和 7危险值 testWithThreshold(6); testWithThreshold(7); } private static void testWithThreshold(int threshold) { UNTREEIFY_THRESHOLD threshold; size 7; // 初始节点数为 7恰好在阈值边界 isTree false; // 初始为链表 treeifyCount 0; untreeifyCount 0; int iterations 10000; // 交替增删的循环次数 long start System.nanoTime(); for (int i 0; i iterations; i) { // 模拟一次 put 操作增加一个节点 size; if (!isTree size TREEIFY_THRESHOLD) { treeify(); // 触发树化 isTree true; } // 模拟一次 remove 操作减少一个节点 size--; if (isTree size UNTREEIFY_THRESHOLD) { untreeify(); // 触发退化 isTree false; } } long end System.nanoTime(); System.out.printf(退化阈值 %d\n, UNTREEIFY_THRESHOLD); System.out.printf( 树化次数 %d, 退化次数 %d\n, treeifyCount, untreeifyCount); System.out.printf( 耗时 ≈ %.2f ms\n\n, (end - start) / 1_000_000.0); } /** 模拟树化操作计入开销 */ private static void treeify() { treeifyCount; // 模拟 CPU 消耗例如红黑树的旋转、节点转换等 for (int i 0; i 1000; i) { Math.sqrt(i); } } /** 模拟退化操作计入开销 */ private static void untreeify() { untreeifyCount; // 模拟 CPU 消耗例如将树节点转为链表节点 for (int i 0; i 1000; i) { Math.sqrt(i); } } }运行结果预期退化阈值树化次数退化次数耗时ms610~ 271000010000~ 20000具体耗时不固定。解释假设现在某个哈希桶里的节点数刚好是 7。此时进来一个并发请求put节点变成 8触发树化遍历链表、创建树节点、左旋右旋疯狂消耗 CPU。下一毫秒又进来一个请求remove节点变回 7触发退化销毁树、重新串成链表再次疯狂消耗 CPU。如果系统恰好在这个边界值7和8之间反复执行增删你的哈希桶就会在“链表”和“红黑树”之间疯狂来回变形。这种现象在工程上叫做状态震荡Thrashing系统会因为无意义的结构转换直接卡死当阈值为6时第一次put树化后节点数变为 8随后remove回到 7但此时7 ≤ 6不成立不会退化。后续循环中节点数只在 7 和 8 之间跳动而结构始终保持树状态因此不再触发任何转换仅发生一次树化。秒懂案例这就像你家里的变频空调。 你把目标温度设为 26 度。 如果空调在 26.1 度时立刻启动制冷在 25.9 度时立刻停机。那你的空调压缩机就会每隔几秒钟“轰——停——轰——停”不出一天就烧坏了。 真正的空调策略是27 度才启动制冷相当于达到 8 变树降到 25 度才停机相当于降到 6 退化。中间的这个差值保护了压缩机CPU免受频繁切换的折磨。所以中间必须隔着一个7 作为缓冲带。 8 才变树即使删了一个变成 7它依然保持树的形态只有降到 6 才退化。这就极大地降低了极端情况下的变形频率。节点数量 N │ 8 ├──────────────────────► 【触发转换】将链表重构成红黑树 (耗时高) │ ▲ 7 ├─ (缓冲地带安全区) │ (如果是 7会在这里上下疯狂震荡) │ ▼ 6 ├──────────────────────► 【触发退化】将红黑树拆解回链表 (耗时高) │ 5 ├─ (普通的链表形态) │接下来就是扩容机制当数据越存越多默认的16个格子肯定不够用冲突会越来越严重。这里逐步拆解putVal中的扩容源码// ... (前面的 put 逻辑执行完后) // size 是当前 HashMap 里总共存了多少个键值对 // threshold 叫做扩容阈值容量 16 * 负载因子 0.75 12 // 【关键源码】当总个数大于阈值时触发扩容 if (size threshold) resize(); // 调起扩容这个巨无霸方法扩容的核心是新建一个大一倍的数组比如从16变成32然后把老数组的所有数据重新算一遍Hash一个个搬到新的数组里这是一个很消耗性能的操作。注意threshold 叫做扩容阈值容量 16 * 负载因子 0.75 12也就是说数组明明有16个格子但是JDK不等装满16个才去扩容而是装到12个的时候就提前扩容了。这里设计一个问题为什么JDK不把负载因子设为1.0装满16个再扩容而是设为0.75提前扩容如果要等要装满16个再扩容会怎么样核心就是装的越满哈希冲突的概率就直线上升。并且哈希散列是随机的假设有16个完全独立的单人间Hash桶。当把12个数据存进去时并不是前12个房间刚好一人一间。真实情况是有几个房间是空的有几个房间住了一个人而某几个房间可能已经挤了两三个人形成了链表。如果负载因子是1.0等到存满16才开始扩容为了填满最后那几个空房间必然会导致大量的新数据撞进已经有人的房间原本O(1)多擦华讯会因为链表过长退化为O(N)。这是牺牲时间换空间。如果负载因子是0.5存8个就扩容这样做冲突确实是少了但是数组里永远有一半以上的格子是空的这是牺牲空间换时间。设置为0.75的真想这个是经严格数学统计泊松分布得出的黄金折中点。当容量达到75%时扩容既不会浪费太多内存又能把链表长度极大概率控制在极短的范围内。扩容详情当元素个数达到12个(16*0.75)系统触发resize()。扩容的第一步很简单开辟一个新数组长度翻倍从16变成32。真正的噩梦是第二步老数组里的数据怎么搬到新数组呢最笨的做法事把老数组的每个key取出来用心的数组长度32重新做一遍(32-1)hash算出一个新的下标这个方法叫做全量中哈希非常消耗CPU。但是JDK作者利用了长度是2的幂次方这个物理特性用位运算彻底免去了重新计算Hash的过程。来看看resize源码是怎么实现的// 遍历老数组的每一个格子 for (int j 0; j oldCap; j) { NodeK,V e oldTab[j]; if (e ! null) { // 如果这个格子是一条链表准备把它拆成两条链表高位链表和低位链表 NodeK,V loHead null, loTail null; // 低位链表 (留在原地的) NodeK,V hiHead null, hiTail null; // 高位链表 (需要搬家的) do { // 【全场最核心源码】决定一个节点是留是走的“上帝之手” // e.hash 是原生 Hash 值oldCap 是老数组的长度 (比如 16) if ((e.hash oldCap) 0) { // 结果等于 0 的挂进低位链表原下标留守 // ... (尾插法代码省略) } else { // 结果不等于 0 的挂进高位链表原下标 老容量 // ... (尾插法代码省略) } } while ((e e.next) ! null); // 遍历完后把两条打碎的链表分别挂到新数组的两个位置上 if (loTail ! null) { newTab[j] loHead; // 原下标不动 } if (hiTail ! null) { newTab[j oldCap] hiHead; // 新下标 老下标 16 } } }这里面最核心的就是((e.hash oldCap) 0)这一段代码。推演开始 假设老容量oldCap 16它的二进制是0001 0000第 5 位是 1其余全是 0。 当你用e.hash 16时本质上只是在看 Hash 值的第 5 位到底是 0 还是 1如果第 5 位是0(e.hash 16) 0成立。 它在新数组容量32掩码310001 1111里计算下标时结果跟原来一模一样。所以它不需要搬家留在老下标j。如果第 5 位是1(e.hash 16) 0不成立。 它在新数组里计算下标时因为第 5 位多了一个1在十进制里刚好代表加上了16。所以新下标直接就是老下标j oldCap。这里是一个实现的代码案例可以参考import java.util.ArrayList; import java.util.List; /** * 演示 HashMap 扩容时利用 (e.hash oldCap) 决定链表拆分的原理。 * 当 oldCap 16 时该运算仅检查 hash 值的第 5 位bit 4。 * 若为 0 → 留在原索引若为 1 → 移动到 (原索引 oldCap)。 */ public class ResizeDemo { // 模拟 HashMap 中的 Node 节点简化版 static class Node { final int hash; final String key; Node next; Node(int hash, String key) { this.hash hash; this.key key; } Override public String toString() { return key (hash hash ); } } public static void main(String[] args) { int oldCap 16; // 老数组容量 int newCap oldCap 1; // 新数组容量 32 // 1. 构造老数组只在一个桶中放入链表便于观察 Node[] oldTab new Node[oldCap]; // 在索引 0 的位置构造一个包含 4 个节点的链表 // 选择 hash 值使得第 5 位bit 4分别为 0 和 1 Node n1 new Node(0, A); // 0 16 0 → 低位 Node n2 new Node(16, B); // 16 16 16 → 高位 Node n3 new Node(32, C); // 32 16 0 → 低位 Node n4 new Node(48, D); // 48 16 16 → 高位 // 串联成链表顺序A - B - C - D n1.next n2; n2.next n3; n3.next n4; oldTab[0] n1; System.out.println( 老数组 (容量 oldCap ) ); printBucket(oldTab, 0); // 2. 执行扩容拆分核心逻辑 Node[] newTab new Node[newCap]; for (int j 0; j oldCap; j) { Node e oldTab[j]; if (e ! null) { // 低位链表头尾 Node loHead null, loTail null; // 高位链表头尾 Node hiHead null, hiTail null; do { // 【关键判断】只检查 hash 值的 oldCap 位即第 5 位 if ((e.hash oldCap) 0) { // 低位留在原索引 if (loTail null) { loHead e; } else { loTail.next e; } loTail e; } else { // 高位移动到 (原索引 oldCap) if (hiTail null) { hiHead e; } else { hiTail.next e; } hiTail e; } 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; // 原索引 oldCap } } } // 3. 打印新数组的桶分布 System.out.println(\n 新数组 (容量 newCap ) ); printBucket(newTab, 0); printBucket(newTab, oldCap); // 即索引 16 // 4. 验证用新掩码 (newCap-1) 计算索引确认与拆分结果一致 System.out.println(\n 验证使用新掩码计算索引 ); int mask newCap - 1; // 31 for (Node node : new Node[]{n1, n2, n3, n4}) { int newIdx node.hash mask; System.out.printf(hash%-3d → 新索引 %d\n, node.hash, newIdx); } } /** 打印指定桶中的链表 */ private static void printBucket(Node[] table, int index) { Node head table[index]; if (head null) { System.out.printf(桶[%d] : (空)\n, index); return; } ListString keys new ArrayList(); Node cur head; while (cur ! null) { keys.add(cur.key); cur cur.next; } System.out.printf(桶[%d] : %s\n, index, String.join( - , keys)); } } 老数组 (容量16) 桶[0] : A - B - C - D 新数组 (容量32) 桶[0] : A - C 桶[16] : B - D 验证使用新掩码计算索引 hash0 → 新索引 0 hash16 → 新索引 16 hash32 → 新索引 0 hash48 → 新索引 16原来 1 班长度 16有 10 个学生现在学校建了新楼要把 1 班拆分成 1 班和 17 班新容量 32。笨办法全量 Rehash把 10 个学生叫出校门让校长重新查户口一个一个重新分配。JDK 的办法直接看学生的学号。规定学号倒数第 5 位是 0 的坐在原地不许动依然是 1 班学号倒数第 5 位是 1 的收拾书包直接搬去 17 班老房号 16一秒钟完成分班没有任何多余计算假设老下标 j 5 (二进制 0101)。当前链表挂着 A 和 B 两个节点。 A 的原生 Hash 尾部 : 0000 0101 (第 5 位是 0) B 的原生 Hash 尾部 : 0001 0101 (第 5 位是 1) 执行 (hash oldCap) 即 (hash 16) 16 的二进制 : 0001 0000 A : 0000 0101 0001 0000 0000 0000 (等于 0) ──► 原地不动新数组下标依然是 5 B : 0001 0101 0001 0000 0001 0000 (不等于0) ──► 需要搬家新数组下标 5 16 21 完美把一个长链表极其均匀地撕裂成了两条短链表JDK 这种扩容设计不仅极其快而且非常巧妙地把冲突的链表打散了。其实还可以更简单static class NodeK,V implements Map.EntryK,V { // 【关键源码】看这个 final // HashMap 把算好的 hash 值作为 final 变量永远存在了节点里 final int hash; final K key; V value; // ... }因为有final int hash这行代码每次扩容时JDK根本不需要重新去算一遍字符串的 Hash而是直接把节点里存着的这个 32 位数字掏出来直接拿它的第 5 位或者第 6 位看一眼就行了具体第几位需要看具体Hash值因为这个final int hash被缓存了下来扩容时不需要重新计算 Key 的哈希值只需要做一次位运算(e.hash oldCap)就能决定去留。这也是为什么HashMap 要求 Key 不可变——一旦 Key 变了缓存的 Hash 就废了。就好比假设学校只有 9 个班。你的学号是1503前两位 15 是入学年份03 是班级。 因为只有 9 个班教务系统只看最后 1 位所以你分在3 班。那个0没人在乎。 后来学校扩建到了 19 个班。教务系统升级必须看最后 2 位了 此时系统一看你的学号1503倒数第二位是0那你还是3 班。 但如果有个人学号是1513以前只看最后 1 位他也在3 班现在看最后 2 位他瞬间就被分去了13 班3 10他的学号变过吗没有只是教务系统看的位数变多了老数据为什么不能呆在原地为什么要拆链表核心思想一如果老数据不搬家你再也找不到它了我刚开始就在想为什么不能不分开让老数据在老房间新数据放新房间后来知道但在数学里这会导致数据彻底丢失为什么因为找数据get方法的公式也变了寻找数据的公式永远是下标 (容量 - 1) hash。原来容量 16 时你把 B 放在了 5 号房间。现在扩容到 32 了如果你不给 B 搬家让它死死留在 5 号房间。灾难降临明天你想把 B 取出来。系统执行get(B)此时容量已经是 32 了系统用新的公式(32 - 1) B的hash一算算出来的结果是21。系统跑到 21 号房间一看空的系统直接告诉你“对不起找不到 B”结论扩容不仅是多盖了房间更是整个寻址公式的升级既然公式升级了所有老数据必须按照新公式重新落座搬家否则就成了没人找得到的“孤魂野鬼”核心思想二拆分链表是为了拯救性能发生扩容的根本原因就是因为房间满了冲突太多了链表太长了 如果在 5 号房间原本挤了 8 个节点现在扩容了你把这 8 个节点全部原封不动搬到一个新房间那链表还是 8 个节点查询还是慢得要死扩容还有什么意义呢 所以利用(e.hash oldCap) 0这个规律把原本挤在一个房间的 8 个人打碎分成两拨4 个人留在 5 号房间4 个人搬去 21 号房间。一条长链表瞬间被撕裂成两条短链表查询速度直接翻倍这才是扩容的终极目的如果老数据不搬家会发生什么 存入 B 时 (cap16): 下标 (16-1) B的Hash尾巴(0001 0101) 5 B 被放在了 [5 号格子]。 发生扩容 (cap 变成 32)。但你执意让 B 留在 5 号格子不动。 读取 B 时 (cap32): 下标 (32-1) B的Hash尾巴(0001 0101) 21 系统去 [21 号格子] 找 B。 结果返回 null 数据凭空“消失”了实战场景老容量oldCap 32它的二进制是0010 0000注意那个1在第几位。有一个数据原来挂在老数组的10 号格子。现在扩容翻倍新容量变成了 64。我们从这个节点的源码里掏出它永远不变的原生 Hash看它的二进制最后 8 位是0110 1010。拿着这个0110 1010去和oldCap (32)也就是0010 0000做按位与计算结果是等于 0 还是不等于 0这个数据是留守在 10 号格子还是搬家去新的格子如果是搬家新格子是多少号第一步做按位与运算判断留还是走我们把 Hash 值和老容量oldCap 32上下对齐原生 Hash 尾巴 : 0 1 1 0 1 0 1 0 oldCap (32) : 0 0 1 0 0 0 0 0 (死死盯住第 6 位的那个 1) ---------------------------------------- 最终运算结果 : 0 0 1 0 0 0 0 0结论因为上下第 6 位都是1所以结果是0010 0000十进制的 32。结果不等于 0源码规定只要(e.hash oldCap) ! 0就必须搬家进入高位链表。你的第一步判断完全正确第二步搬去几号房间可以看我上面贴出的那行核心源码newTab[j oldCap] hiHead;源码写的清清楚楚搬家的新下标公式是老下标 老容量。老下标j 10老容量oldCap 32新下标 10 32 42也就是说最终是要到42下标的~以上就是本篇全部内容啦相信从哈希第一篇到现在已经对哈希的源码有了一点初步的了解后续还是会持续更新我们下篇见~