HashMap 原理
JDK 8+：数组 + 链表 + 红黑树；非线程安全。详解 集合框架。
结构
table[] ──► [k1,v1] → [k9,v9] → null （链表）
──► 红黑树（桶内节点 ≥ 8 且 table.length ≥ 64）
──► null
| 参数 | 默认值 | 说明 |
|---|---|---|
| 初始容量 | 16 | 必为 2 的幂 |
| 负载因子 | 0.75 | 元素数 > capacity×0.75 时扩容 |
| 扩容 | 2 倍 | rehash 到新数组 |
put 流程（简述）
- 计算
hash = (h = key.hashCode()) ^ (h >>> 16)（扰动，减少碰撞） index = (n - 1) & hash定位桶- 桶空 → 直接放入
- 桶非空 → 比 key（先 hash 再
equals）- 相同 key → 覆盖 value
- 不同 key → 挂链表/插入红黑树
- 超阈值 → resize 扩容
链表转红黑树
| 条件 | 说明 |
|---|---|
| 链表长度 ≥ 8 | 且 table.length ≥ 64 时树化 |
| 树节点 ≤ 6 | 退化回链表 |
目的：最坏 O(n) 查改降为 O(log n)。
为什么容量是 2 的幂
(n - 1) & hash 等价于对 n 取模，且位运算更快；保证索引均匀分布。
线程不安全
并发 put 可能导致：数据丢失、死循环（JDK7 扩容头插法，已修复）、size 不准。
| 场景 | 替代 |
|---|---|
| 高并发读写 | ConcurrentHashMap |
| 需排序 | TreeMap |
| 需插入顺序 | LinkedHashMap |
ConcurrentHashMap 简对比
| 版本 | 实现 |
|---|---|
| JDK 7 | Segment 分段锁 |
| JDK 8+ | CAS + synchronized 锁桶头节点，粒度更细 |
常见面试题
Q：HashMap 允许 null 吗？
A：允许 一个 null key、多个 null value；ConcurrentHashMap 不允许 null key/value。
Q：HashSet 如何去重？
A：底层 HashMap，元素作 key，value 为固定 PRESENT；依赖 hashCode + equals。
Q：重写 equals 为什么要重写 hashCode？
A：相等对象 hash 必须相同，否则 HashMap/HashSet 找不到。见 equals与hashCode。
Q：JDK7 和 JDK8 HashMap 区别？
A：8 引入红黑树；扩容 rehash 算法优化；头插改尾插，避免并发扩容环链。