HashMap想解决什么问题？

如果我要存很多 key -> value，最朴素的做法是什么？
用数组或链表，一个个找。

但是这样查不快，最坏要从头找到尾，时间复杂度接近 O(n)。

那怎么让查找更快？
HashMap的做法是：不要“遍历找”，而是直接“算出它该在哪”，这样只需要算一下就能确定他的位置，时间复杂度只有O(1)。

那么靠什么“算”？
靠 hash。这就是 HashMap 的核心想法。

hash 就是把任意数据按照固定规则计算出来的一个整数标识，用来快速定位和查找。

所以结论是：
HashMap 的本质是“通过 key 算位置”，尽量把查找从遍历变成定位。

---

既然要算位置，底层像什么？

什么结构最适合“通过下标直接定位”？
答案是数组。

但是由于算出的位置有可能重合，这就是冲突

冲突了怎么办？
同一个数组位置里，再挂一串节点。

所以就能自己推出：
HashMap 不是单一结构，而是 数组 + 桶内结构。

再追问一步：桶内结构可能是什么？
元素少时用链表，元素多时变红黑树。

所以完整一点是：
HashMap = 数组 + 链表 + 红黑树

---

它怎么从 key 算到数组下标（hash）？

key 能直接当数组下标吗？
不能，类型不一定是整数，而且范围太大。

那第一步是什么？
先把 key 变成一个整数，这就是 hash。

但是只有 hash还不够。数组长度有限，还要把 hash 映射到数组范围内。

所以过程其实是
key -> hash -> index

在 Java 里你可以把它先理解成：

1. key.hashCode() 得到一个整数
2. 再做一次扰动，让高位也参与进来
3. 再映射到数组下标

所以 HashMap 不是“直接存 key”，而是先“算 hash，再定桶”。

---

为什么数组长度总是 2 的幂？

如果数组长度是 16，那下标范围是多少？
0 ~ 15

15 的二进制是1111

如果用 (n - 1) & hash，本质上发生了什么？
只取 hash 的低几位来定位。

这样比 % 有什么好处？
位运算更快。

为什么必须是 2 的幂才好用？
因为这样 n - 1 才会是形如 1111...，低位全是 1，分布更均匀，也方便扩容迁移。

所以你可以记成一句：
数组长度取 2 的幂，是为了让定位更快、分布更稳、扩容更省事。

---

为什么会有链表变红黑树？

如果很多元素都落到同一个桶，链表会越来越长。

链表太长会带来问题：桶内查找会退化，接近 O(n)。

那怎么办？
把链表改成更适合查找的结构。

什么结构更适合？
红黑树，查找能到 O(log n)。

所以树化是为了防止极端冲突时性能崩掉。

 3 个阈值：

• TREEIFY_THRESHOLD = 8
• UNTREEIFY_THRESHOLD = 6
• MIN_TREEIFY_CAPACITY = 64

意思是：
链表够长才考虑树化，但数组太小时通常优先扩容，不急着树化。

---

为什么要扩容？

桶越来越满，会让冲突概率变高。

冲突变高，什么会变慢？
put() 和 get() 都会变慢。

当元素个数超过阈值的时候扩容。

阈值怎么来？
threshold = capacity * loadFactor

默认记住：
容量默认 16，负载因子默认 0.75，所以阈值常见是 12。

为什么不是等到数组满了才扩？
因为那样冲突已经很多了，性能会先变差。

---

扩容时为什么不是“重新乱算一遍”？

数组从 16 扩到 32，元素位置不一定全变。

因为长度翻倍后，只是多看了一位二进制。

问：所以一个元素的新位置通常只有几种可能？
答：两种。

答：要么还在原位置，要么去 原位置 + oldCap

这就是为什么 HashMap 扩容迁移能做得比较高效。
这也是“容量用 2 的幂”的另一个关键收益。

---