JDK8 HashMap源码深度拆解：从数组到红黑树的工程取舍

我干了十年Java开发面试别人时最喜欢问的就是HashMap因为这个问题能很好地看出一个人是背过八股文还是真的理解数据结构的工程取舍。大多数人能脱口而出“数组加链表加红黑树”但一旦问到红黑树为什么是红的黑的、为什么链表长度到8才树化、扩容时旧元素到底怎么迁移很多人就卡住了。这篇文章我打算从JDK源码层面完整拆一遍HashMap从最底层的数组讲起把链表、红黑树、扩容、线程安全这些关键节点全部串起来希望你能从“大概知道”变成“真的讲得清楚”。文章默认以JDK8/11的源码为准中间会穿插JDK7的对比因为很多线上问题、面试题都是围绕这两个版本的差异展开的。适合准备面试的同学也适合想排查线上HashMap相关故障的开发。1. 数组打底HashMap为什么把table做成一张大表1.1 一切定位都发生在数组下标上HashMap最核心的存储结构是一个NodeK,V[] table翻译成人话就是一张存节点的数组。为什么要用数组而不是一开始就上一棵树或者链表因为数组的随机访问是O(1)的只要你知道下标一次寻址就能拿到目标元素。而链表你得从头开始遍历树你得从根节点往下找复杂度差异在数据量大的时候非常明显。那这个下标怎么来答案是哈希。你调用put(key, value)的时候HashMap会先算出key的hash值再用这个hash值去定位落在数组的哪个位置。JDK8里的定位逻辑是这样的if ((p tab[i (n - 1) hash]) null) tab[i] newNode(hash, key, value, null);这里的n是数组长度(n - 1) hash相当于hash % n的位运算版本。举个例子数组长度是16n-1的二进制就是1111任何一个hash值和它做按位与结果只取决于hash的低4位得到的范围一定在0到15之间。这就是一个标准的“散列取模”过程只不过用位运算替代了模运算速度更快。1.2 容量为什么非得是2的幂这可能是HashMap里被问得最频繁的一个点。答案有两条而且两条都成立。第一当数组长度是2的幂时(n - 1) hash才能等价于hash % n。如果数组长度不是2的幂比如是15n-1的二进制是1110最后一位永远是0那么下标永远不可能是奇数这会导致大量槽位被浪费哈希分布极不均匀。第二扩容时的迁移优化依赖这个特性。JDK8在扩容时不需要像JDK7那样重新计算每个元素的hash位置而是通过(e.hash oldCap) 0来判断元素是在原位置还是“原位置oldCap”。这个技巧后面会详细讲它成立的前提就是oldCap是2的幂这样oldCap对应的二进制位只有一个1。所以无论你构造时传了什么容量HashMap都会把你给的数值调整成最接近且大于等于它的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; }你传10进去结果是16传1000结果是1024。1.3 初始容量16和负载因子0.75的由来默认初始容量是16负载因子是0.75。很多人只记结论不知道这背后的权衡。容量小有小的好处内存省坏处是很快触发扩容扩容本身是个耗时的操作。容量大有大的好处扩容频率低坏处是如果只放几个元素内存浪费严重。16这个数字是经验和统计的产物在多数场景下它让HashMap在扩容次数和内存占用之间取得了一个相对均衡的位置。负载因子0.75的意思是当存储的元素个数超过容量 × 0.75时HashMap会扩容。还是以16为例容量乘以负载因子得到threshold12也就是说存到第13个元素时就要扩容。为什么不把负载因子设为1那样空间利用率是高了但hash冲突的概率会显著上升链表会变长查询效率跟着下降。为什么不设为0.5冲突是少了但内存浪费太多一半的格子都空着。0.75是JDK团队用大量测试测出来的一个经验折中值大部分普通场景下不需要动这个参数。我见过有人为了追求性能手动把负载因子调到0.9甚至1.0结果hash分布稍微差一点链表就长得离谱反而更慢。如果不是特殊业务场景建议别乱调。2. hash冲突和链表当两个key落进同一个桶2.1 扰动函数为什么hash要异或高16位(n - 1) hash这个操作有个问题数组长度只有16时n-1的二进制只有低4位是有效的不管你的hash值高位怎么变最终参与下标计算的只有低4位。这会导致大量的高位信息被直接丢弃分布很容易不均匀。比如两个对象的hash值分别是0xFFFF0000和0x00000000它们的低4位完全相同如果直接用 (n-1)hash得到的数组下标是一样的冲突就产生了。JDK8的解决方式是在计算hash时把高16位和低16位做一次异或static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }h 16把高16位搬到低位然后和原来的h做异或。这样哪怕是数组长度很小下标计算时也能掺入高位的差异整体的散列效果会好很多。这就是所谓的“扰动函数”通过一次异或把高位的随机性扩散到低位。还有一个实际的例子String的hashCode算法是s[0]*31^(n-1) s[1]*31^(n-2) ...这也是为什么Aa和BB这两个字符串的hashCode会一样——它们的值是精确计算碰撞的。碰上这种碰撞扰动函数也改变不了事实但至少能在逐个比较之前把判断范围缩小。2.2 桶里挂链表拉链法的具体形态当两个不同key通过hash运算落进同一个数组下标时就发生了哈希冲突。HashMap解决冲突用是经典的“拉链法”数组的每个槽位实际上是一个桶桶里可以挂链表。JDK8的putVal核心逻辑可以这样拆开看if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) // 第一步桶头节点就是要找的key直接覆盖 e p; else if (p instanceof TreeNode) // 第二步桶头节点已经是一棵红黑树了走树的插入逻辑 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); else { // 第三步遍历链表找尾部插入或者在中途找到相同key for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) break; p e; } }注意JDK8插入新节点用的是尾插法链表顺序是新节点在尾部而JDK7用的是头插法新节点直接怼到链表头部。这个差异非常关键后面讲线程安全时还会提到。2.3 为什么是“先hash再equals”很多新手会有一个疑问为什么判断key是否相同时既要比较hash又要调用equals因为hashCode()和equals()的职责不同。hashCode只是用来粗筛它相同不代表两个对象就是同一个key只能说明它们可能落在同一个桶里。真正确定两个key是否相等必须走equals()。所以HashMap的查找过程是先比hashhash不一样就直接跳过从根上避免调用equals的昂贵开销hash一样了再用equals确认是否真的同一个key。如果你自定义了类做key却不重写hashCode和equals那HashMap基本等同于废了。我遇到过不止一次有人用程序员类做key但只重写了equals没重写hashCode结果明明内容一样的对象因为hashCode不同被散列到了不同的桶get永远返回null。这是HashMap用得最频繁的一种低级事故务必记住做HashMap的keyhashCode和equals必须同时重写并且保证equals相等的两个对象hashCode一定相等。3. 链表过长怎么办红黑树何时接管一条长链3.1 链表阈值8并不是拍脑袋定的链表查找是O(n)数据量小问题不大可一旦某个桶的链表变得很长查询效率就会直线下降。JDK8引入了红黑树来兜底树化条件是binCount TREEIFY_THRESHOLD - 1也就是链表长度达到8时会尝试转树。阈值8是官方给的一个统计值不是随便定的。JDK源码注释里有一段概率分析假设hash分布符合泊松分布当负载因子取0.75时链表长度达到8的概率大约是千万分之六。换句话说如果你的hash函数是好的数据分布是均匀的正常情况下桶里的链表长度几乎不可能超过8。一旦真的超过了8基本可以断定hash函数有问题或者有人在故意制造hash碰撞比如恶意构造大量hashCode相同的字符串导致拒绝服务攻击。所以8这个阈值本质上是一个“安全线”过了这条线HashMap认为“出事了”必须用更复杂的数据结构来兜底查询性能。但这里有个容易忽略的细节链表长度达到8时HashMap并不会立刻树化它还要检查当前数组长度是否小于64final void treeifyBin(NodeK,V[] tab, int hash) { int n, index; NodeK,V e; if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize(); else if ((e tab[index (n - 1) hash]) ! null) { // 树化流程 } }如果数组长度没到64HashMap会选择扩容而不是树化。原因也很好理解容量太小意味着冲突主要是“数组太小”导致的此时把数组扩大一倍让原本挤在一个桶里的元素分散到更多桶里效果比引入红黑树更直接、更便宜。只有容量已经超过64仍然出现长链表才说明冲突是“hash本身的问题”树化才有必要。3.2 为什么不直接上AVL树或普通搜索树红黑树是一种自平衡二叉搜索树查找、插入、删除的复杂度都是O(log n)。但要说平衡程度它并不如AVL树AVL对树高的要求更严格左右子树高度差不能超过1而红黑树只要求“最长路径不超过最短路径的两倍”。那HashMap为什么偏偏选了红黑树答案藏在“写操作的成本”里。AVL的平衡维护太激进每次插删都可能引发多次旋转对于频繁put/remove的HashMap来说成本太高。红黑树的平衡条件更宽松插入时最多旋转两次删除时最多旋转三次在查找效率和旋转代价之间取了一个更务实的点。普通二叉搜索树就更不用提了如果插入的数据恰好是递增的它会直接退化成一条链表树的高度变成n查找回到O(n)比不树化还惨。红黑树能保证树高被控制在O(log n)级别靠的是五条约束每个节点要么红要么黑根节点是黑的所有叶子节点都是黑红色节点的子节点必须是黑的从任一节点到其每个叶子节点的路径上黑色节点数量相同。正是最后一条让最长路径不可能超过最短路径的两倍。实际开发中我们很少直接感知到红黑树的插入细节但理解它的旋转平衡机制对理解HashMap的边界行为还是有帮助的。树化之后桶内不再是一个简单的单向链表而是一棵TreeNode组成的树结构TreeNode继承自LinkedHashMap.Entry所以它既有链表的前后指针又有树的parent/left/right指针。3.3 为什么退化阈值设定成6而不是7有了树化就必然要考虑反树化。当某个桶经过扩容或者删除操作后红黑树里的节点数降下来一直保持树结构就有点浪费了毕竟TreeNode本身比普通Node多好几个指针字段内存开销更大。JDK8的设定是节点数降到6时红黑树会转换回普通链表。问题来了为什么树化阈值是8反树化阈值却是6中间为什么留了一个“7”的缓冲区间如果反树化阈值也是8就会出现一个容易反复横跳的场景一个桶的节点数在7、8之间震荡插入一个就树化删除一个就链化来回折腾不仅性能差内存也会频繁分配释放。设成6和8相当于给“要不要切换数据结构”设置了一个迟滞区间避免系统在两个数据结构之间抖动。这种设计在工程里非常常见比如做监控告警的时候CPU超过90%告警、降到70%才恢复中间会留一个回差原理一样。扩容时红黑树也会被拆分。因为扩容后数组长度翻倍原本落在同一个桶的节点会有一部分分到新槽位去这时树里节点数可能不足6HashMap会调用untreeify方法把它还原成普通链表。4. resize扩容翻倍数组背后的元素迁移逻辑4.1 扩容的触发条件和执行过程容量不够就扩容这基本是每个动态集合的通用套路。HashMap的扩容触发点是put完成后如果存储的元素总数超过了threshold就执行resize()。默认情况下 threshold 当前容量 × 负载因子。resize()做的事情大体分两步第一步是算出新容量和新阈值新容量是旧容量的两倍第二步是遍历旧数组把每个桶中的元素迁移到新数组对应位置。JDK7时代的迁移逻辑比较粗暴遍历每个节点重新计算它在新数组中的下标然后重新插到对应桶的头部。这种方式有两个隐患一是重新计算hash有额外开销二是多线程并发扩容时可能产生循环链表。JDK8对迁移逻辑做了优化核心思想是旧容量是2的幂扩容后容量翻倍那么一个节点在新数组中的下标只有两种情况——要么保持原下标要么变成“原下标 旧容量”。判断依据就是(e.hash oldCap) 0。这是什么原理我们回忆一下下标计算用的是(n-1) hash。扩容前n是oldCap扩容后n是oldCap的两倍对应的n-1相当于在原来二进制的基础上向左多了一位1。比如 oldCap16n-11111扩容后 newCap32n-111111。多出来的这一位正好对应oldCap的二进制位。如果hash的这个比特位是0扩容后的下标和原下标相同如果是1新下标就是原下标加上oldCap。这个特性让JDK8在扩容时完全不需要重新计算hash只需要用老的hash值和oldCap做一次按位与就能把一条链表拆成“低位链”和“高位链”两条然后直接挂到新数组的新旧位置上。整个过程高效且不会有JDK7那种“头插反转链表”的问题。4.2 JDK8扩容拆链的具体实现拆链的代码不复杂但很值得细看NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,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; }这里lo表示低位链原下标hi表示高位链原下标oldCap。注意它用的是尾插法保持原有顺序不会出现链表反转。如果桶里是一棵红黑树也会按照同样的思路拆成两根双向链表再分别判断拆分后每根链表的长度是否需要untreeify。4.3 提前指定容量的价值了解了扩容的实现你就明白了为什么建议在构造HashMap时如果能够预估数据量尽量传一个初始化容量。扩容的本质是把旧数组的数据搬到新数组哪怕JDK8优化得再好也是一次O(n)级别的全量操作数据量大的时候能明显感觉到停顿。预估容量的正确姿势并不是“我大概要放100个元素就传100”因为HashMap会把你传的数值调整成最接近的2的幂。比如你预估1000条数据构造时传1000实际容量会被调整成1024threshold变成768。如果预估容量是768那么存到第769个元素时就会扩容最好直接留出安全空间。实际操作中我会按预计数据量 / 0.75 1来计算initialCapacity省得频繁扩容。下面对比一下JDK7和JDK8在扩容、插入、安全性上的差异对比项JDK7JDK8底层结构数组链表数组链表红黑树新节点插入位置链表头部头插法链表尾部尾插法扩容时元素迁移重新hash后头插通过高位运算原地拆链并发扩容死循环风险容易形成循环链表不会形成循环链表数据丢失风险存在仍然存在5. 并发场景下HashMap的短板和替代方案5.1 “HashMap为什么线程不安全”的三个层面网上关于HashMap线程不安全的文章很多但大多数都集中在“JDK7扩容死循环”这一个点。实际上不看版本HashMap线程不安全存在三个层面。第一数据丢失。比如两个线程同时执行put同时发现数组的同一个桶位是空的然后各自创建一个新节点往里写。后写的覆盖先写的另一个线程插入的key就凭空消失了没有任何报错。这就是典型的丢失更新。第二结构破坏。扩容时多个线程一起执行resize旧数组中的链表可能被多个线程同时拆分和重链接JDK7里经典的环形链表就是这种并发修改结构造成的。一旦形成环形链表get一个不存在的key时会陷入死循环CPU直接飙到100%。JDK8改用尾插法后环形链表不会出现了但数据错乱、覆盖丢失的问题依旧存在。第三迭代遍历的一致性。如果你在使用迭代器的过程中别的线程修改了HashMap的结构modCount会变迭代器检测到变化后会立即抛出ConcurrentModificationException。这不是Bug这是fail-fast机制目的是让你尽早发现自己在一个被并发修改的集合上做了错误操作。5.2 替代方案从Hashtable到synchronizedMap再到ConcurrentHashMap既然HashMap不安全那并发场景下该用什么很多人第一反应是Hashtable因为它是线程安全的。但实际上Hashtable是早期的产物它把所有公共方法都用synchronized关键字锁住相当于给整个Hash表上了一把全局大锁。并发一高所有线程都在等锁性能极差。Collections.synchronizedMap的思路和Hashtable类似也是锁整个Map对象。它适合低并发的场景写起来简单但高并发下同样是瓶颈。真正的高并发方案是ConcurrentHashMap。JDK7的ConcurrentHashMap用了一个“分段锁”的设计把整个Map分成16个Segment每个Segment管理一部分桶读写时只锁对应的Segment不同Segment之间可以并行操作。这比全局锁并发度高了不少但锁的粒度还是“一段”而且一些跨段的操作比如size()统计需要遍历所有Segment加锁成本不低。JDK8的ConcurrentHashMap砍掉了Segment直接把synchronized锁在数组的每个桶节点上也就是说锁粒度缩小到了单桶级别。插入的时候如果桶位是空的通过CAS操作直接写入连锁都不需要只有桶位已经有元素时才对桶头节点加synchronized锁。这个设计在绝大多数场景下并发度接近极限——不同桶的写入互不干扰。5.3 什么时候用哪个Map我给一个比较实用的选择清单单线程环境下直接用HashMap别为了防未来可能出现的并发问题提前上ConcurrentHashMap因为ConcurrentHashMap在单线程下反而因为更多的同步和尺寸统计逻辑而略慢一点读多写少的并发场景可以用ConcurrentHashMap如果是读远远多于写且数据量不大也可以用CopyOnWrite做读快照但写成本高如果只是需要一个线程安全的Map并且并发量很低Collections.synchronizedMap也能用只是别对它有太高性能期待。我个人的处理习惯是业务代码里出现的Map凡是可能被多线程共享读取、单线程写入的统一用ConcurrentHashMap这是个很低成本的安全习惯。凡是只在方法内部使用的临时Map用HashMap图它快且简单。实际排查线上问题时线程不安全带来的症状往往是隐蔽的比如偶发性的key丢失、size对不上、偶尔抛个ConcurrentModificationException。如果你们系统用的是JDK7并且HashMap是共享的遇到CPU飙升先别急着怀疑线程池先把线程dump拉出来看看有没有卡在HashMap的get或transfer方法上的——我见过不止一次那个栈基本可以一眼定罪。最后补充一个很多文章不提的实操细节自定义对象做HashMap的key时如果它内部某个参与hashCode的字段会被修改那么这个对象一旦put进Map它的哈希“身份”就变了后续get时用同样的逻辑定位不到原来的桶等于这个key就找不回来了。这跟线程安全无关纯粹是可变key导致的坑。所以作为key的类最好设计成不可变的真要变就老老实实remove之后再put。HashMap这套从数组到链表再到红黑树的演进本质上就是在和“低效”这件事不断对抗用数组保证基础定位速度用链表容忍冲突用红黑树防止最坏情况的退化。理解了每一步是为解决什么问题而存在的你自然就明白8、6、64、0.75这些数字的来历了。