说起HashMap，不少小伙伴第一反应是"能存键值对的容器"，但它底层可不是单一结构在"单打独斗"，而是数组、链表、红黑树组成的"合租天团"。今天就扒一扒这个天团是怎么分工协作，把数据存得又快又稳的——毕竟好的合租关系，核心就是"不挤、不吵、找东西快"。
画个重点：HashMap的底层逻辑，本质是"先按地址分房，人少凑活住，人多就规范排序"。对应的就是：数组负责划分基础区域（分房），链表负责解决区域冲突（凑活住），红黑树负责优化拥挤区域（规范排序）。咱们逐个介绍这三位"租客"。
1号租客：数组——底层的"承重墙"
数组在HashMap里，就像小区里的一栋栋单元楼，每栋楼有自己的编号（专业名叫"索引"），每栋楼里能住数据（键值对）。为什么选数组当承重墙？因为数组的优势太明显了：按编号找楼，速度是O(1)，相当于你知道朋友住3号楼，直接过去就行，不用挨个问。
但问题也很直接：数组的"房间"是固定的，而且每间房理论上只能住一个数据。如果两个数据非要住同一间房（专业名叫"哈希冲突"，比如两个键计算出的索引一样），总不能把人家赶走吧？这时候就需要2号租客救场了。
2号租客：链表——冲突时的"上下铺"
链表就是来解决"一房多客"问题的，它像个可伸缩的上下铺，一旦某间房（数组索引）被占了，新来的 data 就直接"挂"在后面，形成一条链。比如3号楼本来住了数据A，后来数据B也算出索引是3，就跟A说"兄弟挤挤"，挂在A后面；数据C再来，就挂在B后面，以此类推。
这个设计确实解决了冲突，但缺点也很扎心：链表是"一根筋"的结构，找东西只能从头挨个问（遍历）。如果3号楼的上下铺挂了几十上百个数据，你要找最末尾的那个，就得从A问到Z，速度直接降到O(n)，相当于在拥挤的出租屋里找东西，翻来翻去半天找不到，效率低得离谱。
所以链表只能解决"有没有地方住"的问题，解决不了"住得舒服、找得快"的问题。这时候，3号租客——红黑树就该登场了。
3号租客：红黑树——拥挤时的"电梯房改造"
红黑树的作用，就是把"挤爆了的上下铺"改造成"电梯房"。HashMap里有个规矩：当某条链表的长度超过8（默认阈值），而且数组的长度大于64时，这根"乱糟糟的链子"就会被自动改造成红黑树。
红黑树是一种平衡二叉搜索树，自带"排序+快速查找"buff，找数据的速度能降到O(logn)。相当于原来的上下铺被拆了，改成了有排序规则的电梯房，每个数据都有固定的位置，你要找某个数据，不用挨个问，直接按规则找楼层（二分查找思路），效率直接起飞。而且红黑树还会自动保持平衡，不会出现"一边楼很高，一边楼很矮"的情况，保证每个数据的查找速度都稳定。
天团协作全流程：用一个例子讲明白
咱们用一个生活化的例子串一遍流程，你就彻底懂了：
-
你要存一个键值对（“姓名”：“张三”），HashMap先给"姓名"算个哈希值，再通过哈希值算出对应的数组索引，比如是5——相当于张三被分配到5号楼。
-
如果5号楼没人住，张三直接住进去（数组元素直接存这个键值对）。
-
再存一个键值对（“昵称”：“张三”），计算后发现索引也是5——哈希冲突了，这时候就用链表，把"昵称：张三"挂在"姓名：张三"后面，两人凑活住。
-
接着又存了好几个键值对，都算出索引是5，链表长度涨到了9——超过阈值8，而且数组长度也够64，这时候HashMap就把这条链表改成红黑树，从"上下铺"升级成"电梯房"。
-
后来你删除了几个5号楼的数据，红黑树的节点数少于6，HashMap又会把红黑树改回链表——毕竟人少的时候，上下铺比电梯房更省空间，没必要搞这么复杂。
整个过程就像小区的动态管理：人少的时候怎么方便怎么来，人多了就规范管理，人少了再简化，主打一个"灵活高效"。
可视化一下：HashMap底层结构示意图
光说不练假把式，咱们用图表直观看看这个结构（数组为主体，部分索引挂链表，长链表转红黑树）：
图中索引2对应的是链表（长度9，还没转树），索引3对应的是红黑树（链表长度超过8后转换），其他索引是单个数据，清晰体现了三者的共存关系。
补充知识点：不同JDK版本的HashMap差异
咱们前面聊的"数组+链表+红黑树"组合，其实是JDK 1.8及之后的"升级版合租方案"。在这之前，JDK 1.7的HashMap可是个"老古董"，只靠"数组+链表"撑场面，就像个没有电梯房的老旧小区，住的人多了全是问题。下面咱们用表格直观看看核心差异，顺便唠唠这些差异背后的"优化思路"：
| 对比维度 |
JDK 1.7 |
JDK 1.8及之后 |
| 底层结构 |
数组 + 链表（纯"上下铺"小区，没电梯） |
数组 + 链表 / 红黑树（有"电梯房"改造方案） |
| 哈希冲突解决 |
仅靠链表，冲突多了链表越长，找东西越慢（O(n)） |
链表短的时候凑活住，超过8个节点自动转红黑树（O(logn)），人少了再拆回链表 |
| 扩容逻辑 |
先扩容再插入新数据，容易出现"无效扩容"（比如插完就不用了） |
先插入数据再判断是否扩容，更合理高效，减少无效操作 |
| 并发问题 |
并发扩容时极易出现"链表环"，就像上下铺连成了圈，找东西直接死循环，CPU飙升到100% |
优化了扩容时的链表迁移逻辑，解决了链表环问题，但仍线程不安全（想线程安全还是得用ConcurrentHashMap） |
| 插入方式 |
链表采用"头插法"（新来的人直接占第一个铺，把老人挤到后面） |
链表采用"尾插法"（新来的人乖乖排到队尾，秩序井然） |
|
|
|
这里重点说两个有意思的点：一是JDK 1.7的"头插法"，为啥要改？因为头插法在扩容时容易搞反链表顺序，多线程情况下直接形成死循环，就像大家排队时有人插队还把队伍搅成了圆圈，谁也出不去。JDK 1.8改成尾插法，彻底解决了这个问题。二是红黑树的引入，不是为了"炫技"，而是真的解决了JDK 1.7的"性能瓶颈"——当链表长度超过8，JDK 1.7找数据要从头问到尾，而JDK 1.8转成红黑树后，相当于有了电梯和索引，直接定位楼层，效率天差地别。
另外补充一句，不管哪个版本的HashMap，都有个共同特点：初始容量是16，扩容时都是翻倍（新容量=旧容量×2），而且容量必须是2的幂次方。这就像小区规划，每栋楼的编号都是2的倍数，方便快速找房，本质是为了通过"位运算"快速计算数据该住哪栋楼，提升定位效率。
最后总结：三个结构的核心使命
数组：负责"快速定位"，是整个结构的基础，保证查找的初始效率；
链表：负责"解决冲突"，用灵活的结构容纳同一索引的数据，避免数据溢出；
红黑树：负责"优化效率"，在数据量大的时候提升查找、删除、修改的速度，避免链表的低效遍历。
这三者的组合，让HashMap在"空间"和"时间"之间找到了一个绝佳的平衡点——既不会像纯数组那样浪费空间，也不会像纯链表那样效率低下，这也是它能成为Java里最常用容器之一的核心原因。
<p>说起HashMap，不少小伙伴第一反应是"能存键值对的容器"，但它底层可不是单一结构在"单打独斗"，而是数组、链表、红黑树组成的"合租天团"。今天就扒一扒这个天团是怎么分工协作，把数据存得又快又稳的——毕竟好的合租关系，核心就是"不挤、不吵、找东西快"。</p>
<p>画个重点：HashMap的底层逻辑，本质是"先按地址分房，人少凑活住，人多就规范排序"。对应的就是：<strong>数组负责划分基础区域（分房），链表负责解决区域冲突（凑活住），红黑树负责优化拥挤区域（规范排序）</strong>。咱们逐个介绍这三位"租客"。</p>
<h2><a id="1_5"></a>1号租客：数组——底层的"承重墙"</h2>
<p>数组在HashMap里，就像小区里的一栋栋单元楼，每栋楼有自己的编号（专业名叫"索引"），每栋楼里能住数据（键值对）。为什么选数组当承重墙？因为数组的优势太明显了：按编号找楼，速度是O(1)，相当于你知道朋友住3号楼，直接过去就行，不用挨个问。</p>
<p>但问题也很直接：数组的"房间"是固定的，而且每间房理论上只能住一个数据。如果两个数据非要住同一间房（专业名叫"哈希冲突"，比如两个键计算出的索引一样），总不能把人家赶走吧？这时候就需要2号租客救场了。</p>
<h2><a id="2_11"></a>2号租客：链表——冲突时的"上下铺"</h2>
<p>链表就是来解决"一房多客"问题的，它像个可伸缩的上下铺，一旦某间房（数组索引）被占了，新来的 data 就直接"挂"在后面，形成一条链。比如3号楼本来住了数据A，后来数据B也算出索引是3，就跟A说"兄弟挤挤"，挂在A后面；数据C再来，就挂在B后面，以此类推。</p>
<p>这个设计确实解决了冲突，但缺点也很扎心：链表是"一根筋"的结构，找东西只能从头挨个问（遍历）。如果3号楼的上下铺挂了几十上百个数据，你要找最末尾的那个，就得从A问到Z，速度直接降到O(n)，相当于在拥挤的出租屋里找东西，翻来翻去半天找不到，效率低得离谱。</p>
<p>所以链表只能解决"有没有地方住"的问题，解决不了"住得舒服、找得快"的问题。这时候，3号租客——红黑树就该登场了。</p>
<h2><a id="3_19"></a>3号租客：红黑树——拥挤时的"电梯房改造"</h2>
<p>红黑树的作用，就是把"挤爆了的上下铺"改造成"电梯房"。HashMap里有个规矩：当某条链表的长度超过8（默认阈值），而且数组的长度大于64时，这根"乱糟糟的链子"就会被自动改造成红黑树。</p>
<p>红黑树是一种平衡二叉搜索树，自带"排序+快速查找"buff，找数据的速度能降到O(logn)。相当于原来的上下铺被拆了，改成了有排序规则的电梯房，每个数据都有固定的位置，你要找某个数据，不用挨个问，直接按规则找楼层（二分查找思路），效率直接起飞。而且红黑树还会自动保持平衡，不会出现"一边楼很高，一边楼很矮"的情况，保证每个数据的查找速度都稳定。</p>
<h2><a id="_25"></a>天团协作全流程：用一个例子讲明白</h2>
<p>咱们用一个生活化的例子串一遍流程，你就彻底懂了：</p>
<ol>
<li>
<p>你要存一个键值对（“姓名”：“张三”），HashMap先给"姓名"算个哈希值，再通过哈希值算出对应的数组索引，比如是5——相当于张三被分配到5号楼。</p>
</li>
<li>
<p>如果5号楼没人住，张三直接住进去（数组元素直接存这个键值对）。</p>
</li>
<li>
<p>再存一个键值对（“昵称”：“张三”），计算后发现索引也是5——哈希冲突了，这时候就用链表，把"昵称：张三"挂在"姓名：张三"后面，两人凑活住。</p>
</li>
<li>
<p>接着又存了好几个键值对，都算出索引是5，链表长度涨到了9——超过阈值8，而且数组长度也够64，这时候HashMap就把这条链表改成红黑树，从"上下铺"升级成"电梯房"。</p>
</li>
<li>
<p>后来你删除了几个5号楼的数据，红黑树的节点数少于6，HashMap又会把红黑树改回链表——毕竟人少的时候，上下铺比电梯房更省空间，没必要搞这么复杂。</p>
</li>
</ol>
<p>整个过程就像小区的动态管理：人少的时候怎么方便怎么来，人多了就规范管理，人少了再简化，主打一个"灵活高效"。</p>
<h2><a id="HashMap_42"></a>可视化一下：HashMap底层结构示意图</h2>
<p>光说不练假把式，咱们用图表直观看看这个结构（数组为主体，部分索引挂链表，长链表转红黑树）：</p>
<div id="mermaid-container-41d6df9d1bcd484f8ecf1f32f328cf99"></div><p>图中索引2对应的是链表（长度9，还没转树），索引3对应的是红黑树（链表长度超过8后转换），其他索引是单个数据，清晰体现了三者的共存关系。</p>
<h2><a id="JDKHashMap_76"></a>补充知识点：不同JDK版本的HashMap差异</h2>
<p>咱们前面聊的"数组+链表+红黑树"组合，其实是JDK 1.8及之后的"升级版合租方案"。在这之前，JDK 1.7的HashMap可是个"老古董"，只靠"数组+链表"撑场面，就像个没有电梯房的老旧小区，住的人多了全是问题。下面咱们用表格直观看看核心差异，顺便唠唠这些差异背后的"优化思路"：</p>
<table>
<thead>
<tr>
<th>对比维度</th>
<th>JDK 1.7</th>
<th>JDK 1.8及之后</th>
</tr>
</thead>
<tbody>
<tr>
<td>底层结构</td>
<td>数组 + 链表（纯"上下铺"小区，没电梯）</td>
<td>数组 + 链表 / 红黑树（有"电梯房"改造方案）</td>
</tr>
<tr>
<td>哈希冲突解决</td>
<td>仅靠链表，冲突多了链表越长，找东西越慢（O(n)）</td>
<td>链表短的时候凑活住，超过8个节点自动转红黑树（O(logn)），人少了再拆回链表</td>
</tr>
<tr>
<td>扩容逻辑</td>
<td>先扩容再插入新数据，容易出现"无效扩容"（比如插完就不用了）</td>
<td>先插入数据再判断是否扩容，更合理高效，减少无效操作</td>
</tr>
<tr>
<td>并发问题</td>
<td>并发扩容时极易出现"链表环"，就像上下铺连成了圈，找东西直接死循环，CPU飙升到100%</td>
<td>优化了扩容时的链表迁移逻辑，解决了链表环问题，但仍<strong>线程不安全</strong>（想线程安全还是得用ConcurrentHashMap）</td>
</tr>
<tr>
<td>插入方式</td>
<td>链表采用"头插法"（新来的人直接占第一个铺，把老人挤到后面）</td>
<td>链表采用"尾插法"（新来的人乖乖排到队尾，秩序井然）</td>
</tr>
<tr>
<td></td>
<td></td>
<td></td>
</tr>
</tbody>
</table>
<p>这里重点说两个有意思的点：一是JDK 1.7的"头插法"，为啥要改？因为头插法在扩容时容易搞反链表顺序，多线程情况下直接形成死循环，就像大家排队时有人插队还把队伍搅成了圆圈，谁也出不去。JDK 1.8改成尾插法，彻底解决了这个问题。二是红黑树的引入，不是为了"炫技"，而是真的解决了JDK 1.7的"性能瓶颈"——当链表长度超过8，JDK 1.7找数据要从头问到尾，而JDK 1.8转成红黑树后，相当于有了电梯和索引，直接定位楼层，效率天差地别。</p>
<p>另外补充一句，不管哪个版本的HashMap，都有个共同特点：初始容量是16，扩容时都是翻倍（新容量=旧容量×2），而且容量必须是2的幂次方。这就像小区规划，每栋楼的编号都是2的倍数，方便快速找房，本质是为了通过"位运算"快速计算数据该住哪栋楼，提升定位效率。</p>
<h2><a id="_93"></a>最后总结：三个结构的核心使命</h2>
<p>数组：负责"快速定位"，是整个结构的基础，保证查找的初始效率；<br />
链表：负责"解决冲突"，用灵活的结构容纳同一索引的数据，避免数据溢出；<br />
红黑树：负责"优化效率"，在数据量大的时候提升查找、删除、修改的速度，避免链表的低效遍历。</p>
<p>这三者的组合，让HashMap在"空间"和"时间"之间找到了一个绝佳的平衡点——既不会像纯数组那样浪费空间，也不会像纯链表那样效率低下，这也是它能成为Java里最常用容器之一的核心原因。</p>
