HashMap数据结构
面试里问 HashMap，很多人张口就是“数组 + 链表 + 红黑树”。
但再追问一句：为什么容量必须是 2 的幂？为什么链表到 8 还不一定树化？扩容时元素到底怎么迁移？很多人就开始背八股了。
其实 HashMap 不用死记。你可以把它想成一个快递柜：
数组就是一排柜格，负责快速定位；
hash决定包裹放哪个柜格；
柜格里已经有包裹了，就叫哈希冲突，那就排队，形成链表；
队伍太长，查询太慢，就升级成红黑树；
柜子快装满了，就扩容，换一排更大的柜子重新分配。
下面我们跟着一次put，把 HashMap 的核心机制串起来。
一、一次 put 到底发生了什么？
当你写下：
map.put("张三", 18);HashMap 大概做这几件事：
算出 key 的 hash；
根据 hash 和数组长度算出下标；
看这个位置是不是空的；
空就直接放；
不空就判断 key 是否相等：相等就覆盖 value，不相等就挂到链表或红黑树上；
元素太多就扩容。
一句话：
数组负责定位，链表/红黑树负责处理冲突，扩容负责控制负载。
二、下标是怎么算出来的？
HashMap 最终用这个公式算下标：
int index = (n - 1) & hash;n是数组容量。
这里有两个关键点。
第一，容量必须是 2 的幂。
因为当n是 2 的幂时，n - 1的二进制低位全是 1。比如：
n = 16，n - 1 = 15，二进制是1111；n = 32，n - 1 = 31，二进制是11111。
这样(n - 1) & hash就能均匀保留 hash 的低位，效果类似取模，但位运算更快。
如果容量不是 2 的幂，某些下标可能永远算不到，桶分布会不均匀。所以就算你手动指定了一个不是 2 的幂的初始容量，HashMap 也会帮你调整成最接近的、更大的 2 的幂。
第二，hash 会先扰动一下。
HashMap 不是直接用key.hashCode()，而是把 hash 的高位和低位混合一下，让结果更分散，减少冲突。你不用记具体代码，记住目的就行：让 hash 更散，少撞车。
三、冲突了怎么办？
算出下标后，如果那个位置是空的，直接放。
如果不空，就要处理冲突：
key 相等，覆盖 value；
key 不相等，挂到链表后面；
链表太长，再考虑转红黑树。
这里判断 key 是否相等，不只看 hash，还要用equals()。所以自定义对象当 key 时，hashCode()和equals()要一起正确实现，不然会出现“找不到 key”或者“两个不同 key 被当成同一个”的问题。
四、链表什么时候变红黑树？
很多人只背“链表到 8 就变红黑树”，这是不完整的。
必须同时满足两个条件：
链表长度超过 8；
数组容量至少为 64。
如果链表到了 8，但数组容量还不到 64，HashMap 不会树化，而是先扩容。因为容量小的时候，扩容分散冲突更划算；树化本身也有额外开销。
反过来，红黑树节点减少到 6 时，会退回链表。为什么是 6 不是 8？因为留个缓冲，避免在 7、8 附近来回转换。
可以记成：
8 是树化线，64 是容量门槛，6 是退化线。
红黑树也不用深入理解，你只要知道：它是一种自平衡的树，查起来比长链表快。链表查询要一个个找，红黑树能少走很多步。
五、什么时候扩容？
默认情况下：
初始容量是 16；
负载因子是 0.75；
扩容阈值是
16 × 0.75 = 12。
当元素数量超过 12，就触发扩容。新容量是原来的 2 倍。
扩容最核心的动作是：把旧数组里的元素搬到新数组。
JDK 1.8 用了一个巧办法。容量翻倍后，元素的新位置只有两种可能：
还在原来的下标；
或者变成“原下标 + 旧容量”。
不用每个元素都重新算一遍完整下标。如果旧桶里是红黑树，迁移时会先拆成两个链表，再按新位置分配，必要时重新树化。
扩容的优点是降低冲突、提高查询效率；缺点是要搬元素，元素多时比较耗时。所以如果能预估元素数量，初始化时给一个合适容量，可以减少扩容次数。
六、几个关键参数，一张表记住
| 参数 | 默认值 | 作用 | 常见误区 |
|---|---|---|---|
| 初始容量 | 16 | 桶数组初始长度 | 不是随便设，最终会调成 2 的幂 |
| 负载因子 | 0.75 | 扩容阈值 = 容量 × 负载因子 | 不是越大越好 |
| 树化阈值 | 8 | 链表转红黑树条件之一 | 还要容量 ≥ 64 |
| 反树化阈值 | 6 | 红黑树退回链表 | 留缓冲，避免频繁转换 |
| 最小树化容量 | 64 | 容量不够先扩容 | 小容量树化不划算 |
负载因子 0.75 是时间和空间的平衡：太小会频繁扩容、浪费空间；太大会冲突严重、查询变慢。
七、常见误区，面试别踩
误区一：链表到 8 一定变红黑树。
不对，还要看数组容量是否 ≥ 64。容量不够先扩容。
误区二：容量可以随便指定。
HashMap 最终会把容量调整成 2 的幂，因为下标计算依赖这个特性。
误区三：负载因子越大越好。
负载因子大，空间利用率高，但冲突概率也高，查询会变慢。
误区四：扩容只是把数组变大。
扩容还要搬元素、重新分配位置，成本不低。
八、最后总结
HashMap 的核心就三句话：
用数组快速定位：
(n - 1) & hash算下标，容量必须是 2 的幂。用链表/红黑树处理冲突：冲突少挂链表，冲突严重且容量够大才树化。
用扩容控制负载：超过阈值容量翻倍，元素按规则迁移。
所以 HashMap 平均能做到 O(1) 的查找、插入和删除，不是因为它神奇，而是因为它在数组定位、冲突处理和扩容之间做了一套平衡。
