HashMap 的底层原理是什么？put 和 get 的过程是怎样的？

简化版

HashMap 底层是「数组 + 链表 + 红黑树」。put 时先对 key 的 hashCode 做扰动得到 hash，用 hash & (n-1) 定位到数组某个桶；桶为空就直接放，冲突了就在链表/红黑树里按 equals 找：找到就覆盖，没找到就追加。元素数超过「容量 × 0.75」就扩容成 2 倍。JDK 8 起，链表长度到 8 且数组长度 ≥64 会转红黑树，避免哈希碰撞退化成 O(n)。

详细版

HashMap 用一个 Node[] table 数组存数据，每个数组元素叫一个「桶（bucket）」。核心是把 key 通过哈希映射到某个桶的下标，理想情况下 put/get 都是 O(1)。

put(key, value) 流程：

算 hash：hash = h ^ (h >>> 16)，把 hashCode 的高 16 位异或到低 16 位（叫「扰动函数」），让高位也参与下标运算；
定位桶：下标 i = (n - 1) & hash（n 是数组长度，必为 2 的幂，所以等价于 hash % n）；
放入桶：
- 桶为空 → 直接新建 Node 放进去；
- 桶不为空 → 沿链表/红黑树比对：hash 相等且（key== 或 key.equals()）为真 → 覆盖旧 value；否则追加到末尾；
树化判断：链表追加后若长度 ≥8 且数组长度 ≥64 → 转红黑树；
扩容判断：++size > threshold（threshold = 容量 × 负载因子）→ resize() 扩容 2 倍并 rehash。

get(key) 流程：同样算 hash → 定位桶 → 在链表/红黑树里用 hash + equals 找到节点返回 value，找不到返回 null。

Map<String, Integer> map = new HashMap<>();
map.put("apple", 1);   // 算 hash → 定位桶 → 桶空，直接放
map.put("apple", 2);   // 同 key，equals 命中 → 覆盖，返回旧值 1
Integer v = map.get("apple"); // → 2

⚠️ key 的 hashCode() 和 equals() 必须一致：两个 equals 相等的对象 hashCode 必须相等，否则会定位到不同桶，导致「放进去却取不出来」。

完整版教学

一、为什么需要哈希表：从「数组下标」到「任意 key」

数组能 O(1) 随机访问，但前提是下标必须是「连续整数」。现实里我们想用任意对象（字符串、自定义类）当 key，哈希表就是把这座桥搭起来的结构：用一个哈希函数把任意 key 映射成数组下标。

理想目标：不同 key 映射到不同下标，读写都 O(1)。但映射空间（比如 40 亿个 int hash）远大于数组长度（比如 16），必然有不同 key 落到同一个桶——这就是「哈希冲突」。所以哈希表真正要解决的两件事是：① 怎么把 key 均匀撒到桶里（少冲突）；② 冲突了怎么存（拉链）。HashMap 对这两点的答案分别是「扰动函数 + 2 的幂取模」和「链表/红黑树拉链」。

二、扰动函数：为什么要 `h ^ (h >>> 16)`

下标计算用的是 (n-1) & hash。当 n 较小（比如默认 16），n-1 = 0b1111，这个与运算只保留了 hash 的最低 4 位，高位全被丢弃。如果两个 key 的 hashCode 只有高位不同、低位相同，它们就会撞进同一个桶。

扰动函数把高 16 位异或到低 16 位，让高位信息「混入」低位，参与下标计算，从而降低冲突。看一个具体算例：

key A: hashCode = 0x7F8A_0000
key B: hashCode = 0x0000_0000
不扰动时 (n=16)：
  A: 0x7F8A0000 & 0xF = 0   → 桶 0
  B: 0x00000000 & 0xF = 0   → 桶 0   ← 撞了！
扰动后 hash = h ^ (h>>>16)：
  A: 0x7F8A0000 ^ 0x00007F8A = 0x7F8A7F8A → & 0xF = 0xA → 桶 10
  B: 0x00000000 ^ 0x00000000 = 0x00000000 → & 0xF = 0    → 桶 0    ← 分开了

一次异或成本极低，却能显著改善低位分布，这是「花小钱办大事」的经典设计。

三、put 的完整决策树（含冲突与覆盖）

put 不是简单「往桶里塞」，它要区分「新增」和「覆盖」。用一张判定表看清每条分支：

情况	判断条件	动作
数组未初始化	`table == null`	先 `resize()` 建表
桶为空	`table[i] == null`	直接放新 Node
桶头就是目标 key	`hash 相等 && (== 或 equals)`	覆盖 value
桶是红黑树	`头节点 instanceof TreeNode`	走树的 put
桶是链表	其余	遍历链表：命中则覆盖，到尾未命中则追加
追加后链表过长	`链表长度 ≥ 8 && 数组长度 ≥ 64`	树化
元素总数超阈值	`++size > threshold`	扩容

关键点：判等要求 hash 先相等，再看 equals。hash 是快速筛选（整数比较极快），equals 是精确判定（可能较慢），先 hash 后 equals 是性能优化。

四、扩容 resize：为什么 JDK 8 不用重新取模

当 size > 容量 × 0.75，数组翻倍。老版本要对每个元素重新 hash % newCap 算新位置，JDK 8 发现了一个巧妙规律：容量翻倍后，元素要么留在原下标 i，要么去到 i + oldCap，只取决于 hash 在「新增的那一位」上是 0 还是 1。

oldCap = 16 (n-1 = 0b01111)，newCap = 32 (n-1 = 0b11111)
新增判断位 = oldCap = 0b10000
元素 hash = ...1_0110:  hash & oldCap = 0b10000 ≠ 0 → 新位置 = i + 16
元素 hash = ...0_0110:  hash & oldCap = 0        → 新位置 = i（不动）

于是 JDK 8 把一条链表拆成「低位链（留原地）」和「高位链（去 i+oldCap）」两条，一次遍历完成迁移，避免了对每个元素做除法/取模，效率更高。这也顺带修复了 JDK 7 头插法在并发扩容时可能形成环形链表、导致 get 死循环的著名 bug（JDK 8 改用尾插保持顺序）。

五、树化与退化：链表 O(n) 的兜底

哈希分布再好，也可能被恶意构造的 key（hashCode 全相同）打崩，让某个桶退化成长链表，查询变 O(n)——这是一种 DoS 攻击面。JDK 8 的对策是：同一个桶里链表长度到 8，且数组长度 ≥64 时，把链表转成红黑树，查询从 O(n) 降到 O(log n)。

反过来，扩容或删除让树节点数降到 6 以下，会「退化」回链表（省内存，TreeNode 是普通 Node 的约 2 倍大小）。8 和 6 之间留了个缓冲区，避免元素在阈值附近反复增删导致「树化↔退化」频繁抖动。

桶内退化成长链（未树化）：get 要遍历整条链
桶[5] → n1 → n2 → n3 → ... → n50   查询最坏 O(50)
树化后：
桶[5] → (红黑树根)                  查询最坏 O(log50)≈6 次比较

六、时间复杂度与 hashCode/equals 契约

HashMap 的「平均 O(1)」建立在两个前提上：哈希分布均匀 + 单桶元素少。一旦大量冲突，复杂度会滑向 O(log n)（已树化）甚至 O(n)（未达树化阈值）。

场景	get/put 复杂度
分布均匀，桶内 0~1 个元素	O(1)
冲突较多，桶内是链表	O(链长)，最坏 O(n)
冲突严重，桶内已树化	O(log n)

而这一切的地基是 hashCode/equals 契约：equals 相等 → hashCode 必须相等。如果你自定义类只重写 equals 不重写 hashCode，两个「逻辑相等」的对象会有不同 hashCode，落到不同桶，get 时根本找不到刚 put 进去的值。用可变对象当 key 也很危险：put 之后改了参与 hashCode 的字段，对象会「迷失」在旧桶里。

记忆钩子：「扰动定桶、拉链解冲突、超载就翻倍、过长就变树」——四句话覆盖 HashMap 全部核心机制。

七、常见误区与追问

误区：HashMap 的 get/put 一定是 O(1)。 只有哈希分布均匀时才是；冲突严重时链表 O(n)、红黑树 O(log n)，「O(1)」是平均而非最坏。
误区：链表长度到 8 就一定树化。 还有一个前提——数组长度必须 ≥64；否则优先扩容（扩容能分散冲突），而不是树化。
误区：只重写 equals 不重写 hashCode 也能用作 key。 会导致 put 进去 get 不出来，两方法必须成对重写并保持一致。
误区：HashMap 有序。 它不保证任何顺序，且扩容后顺序还会变；要插入有序用 LinkedHashMap，要排序用 TreeMap。
追问：JDK 7 和 JDK 8 的 HashMap 有什么区别？ JDK 7 是「数组+链表」头插法，并发扩容可能成环导致死循环；JDK 8 是「数组+链表+红黑树」尾插法，扩容用高低位链拆分，修复了成环问题。
追问：HashMap 允许 null 键值吗？ 允许一个 null key（固定放桶 0，hash 直接算 0）和多个 null value；而 Hashtable、ConcurrentHashMap 都不允许 null。
追问：为什么初始容量建议按预估值设为 2 的幂？ 避免频繁扩容 rehash；若预计放 N 个，容量宜设为 N / 0.75 向上取到 2 的幂，减少冲突和扩容拷贝。

八、加强记忆

把 HashMap 想成一排编号的「储物柜（桶）」：扰动函数负责把 key 的柜号算得更分散（高位混低位，避免只看低几位就撞柜）；(n-1) & hash 把柜号压进数组范围（容量是 2 的幂才能用与运算替代取模）；同一个柜子挤了多个 key 就拉链（先 hash 快筛、再 equals 精判，命中覆盖、否则追加）；柜子总占用超过 75% 就翻倍扩容，JDK 8 用高低位链一次拆分迁移、不再逐个取模；某个柜子的链太长（≥8 且数组 ≥64）就升级成红黑树兜底、退到 6 再退化回链表。而这套机制能成立的前提永远是 hashCode/equals 契约和 key 不可变——记住「扰动定桶、拉链解冲突、超载翻倍、过长变树」，再补一句「hashCode 定位、equals 定案」，这道题就答透了。

HashMap 扩容与 rehash 全过程

简化版

详细版