HashMap数据结构

面试里问 HashMap，很多人张口就是“数组 + 链表 + 红黑树”。
但再追问一句：为什么容量必须是 2 的幂？为什么链表到 8 还不一定树化？扩容时元素到底怎么迁移？很多人就开始背八股了。

其实 HashMap 不用死记。你可以把它想成一个快递柜：

• 数组就是一排柜格，负责快速定位；

• hash决定包裹放哪个柜格；

• 柜格里已经有包裹了，就叫哈希冲突，那就排队，形成链表；

• 队伍太长，查询太慢，就升级成红黑树；

• 柜子快装满了，就扩容，换一排更大的柜子重新分配。

下面我们跟着一次put，把 HashMap 的核心机制串起来。

一、一次 put 到底发生了什么？

当你写下：

map.put("张三", 18);

HashMap 大概做这几件事：

1. 算出 key 的 hash；

2. 根据 hash 和数组长度算出下标；

3. 看这个位置是不是空的；

4. 空就直接放；

5. 不空就判断 key 是否相等：相等就覆盖 value，不相等就挂到链表或红黑树上；

6. 元素太多就扩容。

一句话：

数组负责定位，链表/红黑树负责处理冲突，扩容负责控制负载。

二、下标是怎么算出来的？

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 就变红黑树”，这是不完整的。

必须同时满足两个条件：

1. 链表长度超过 8；

2. 数组容量至少为 64。

如果链表到了 8，但数组容量还不到 64，HashMap 不会树化，而是先扩容。因为容量小的时候，扩容分散冲突更划算；树化本身也有额外开销。

反过来，红黑树节点减少到 6 时，会退回链表。为什么是 6 不是 8？因为留个缓冲，避免在 7、8 附近来回转换。

可以记成：

8 是树化线，64 是容量门槛，6 是退化线。

红黑树也不用深入理解，你只要知道：它是一种自平衡的树，查起来比长链表快。链表查询要一个个找，红黑树能少走很多步。

五、什么时候扩容？

默认情况下：

• 初始容量是 16；

• 负载因子是 0.75；

• 扩容阈值是16 × 0.75 = 12。

当元素数量超过 12，就触发扩容。新容量是原来的 2 倍。

扩容最核心的动作是：把旧数组里的元素搬到新数组。

JDK 1.8 用了一个巧办法。容量翻倍后，元素的新位置只有两种可能：

• 还在原来的下标；

• 或者变成“原下标 + 旧容量”。

不用每个元素都重新算一遍完整下标。如果旧桶里是红黑树，迁移时会先拆成两个链表，再按新位置分配，必要时重新树化。

扩容的优点是降低冲突、提高查询效率；缺点是要搬元素，元素多时比较耗时。所以如果能预估元素数量，初始化时给一个合适容量，可以减少扩容次数。

六、几个关键参数，一张表记住

负载因子 0.75 是时间和空间的平衡：太小会频繁扩容、浪费空间；太大会冲突严重、查询变慢。

七、常见误区，面试别踩

误区一：链表到 8 一定变红黑树。
不对，还要看数组容量是否 ≥ 64。容量不够先扩容。

误区二：容量可以随便指定。
HashMap 最终会把容量调整成 2 的幂，因为下标计算依赖这个特性。

误区三：负载因子越大越好。
负载因子大，空间利用率高，但冲突概率也高，查询会变慢。

误区四：扩容只是把数组变大。
扩容还要搬元素、重新分配位置，成本不低。

八、最后总结

HashMap 的核心就三句话：

1. 用数组快速定位：(n - 1) & hash算下标，容量必须是 2 的幂。

2. 用链表/红黑树处理冲突：冲突少挂链表，冲突严重且容量够大才树化。

3. 用扩容控制负载：超过阈值容量翻倍，元素按规则迁移。

所以 HashMap 平均能做到 O(1) 的查找、插入和删除，不是因为它神奇，而是因为它在数组定位、冲突处理和扩容之间做了一套平衡。