今日任务
时间 | 动作 |
|---|---|
| 0-20min | 打开一篇讲HashMap的文章/视频，只看「put流程」和「1.7 vs 1.8区别」，别的先不看 |
20-40min | 拿张纸，画图：数组→链表→红黑树，标注扩容触发条件 |
| 40-60min | 对着图，用自己的话讲一遍（可以录音，回听哪里卡壳） |
| 60-90min | 整理成你自己的答案模板（按“底层结构→put步骤→为什么这样设计→扩容”顺序） |
| 90-120min | 背诵你的模板，直到能连续讲2分钟不卡顿 |
一、HashMap在JDK1.7与1.8的区别
JDK 1.7 与 1.8 的 HashMap 核心区别在于底层数据结构、哈希冲突解决方式及扩容机制，1.8 通过引入红黑树和尾插法显著提升了性能与并发安全性。
核心差异对比
- 底层数据结构
- JDK 1.7：数组 + 单向链表（Entry 数组）。极端哈希冲突下，查询时间复杂度退化为 O(n)。
- JDK 1.8：数组 + 链表 + 红黑树（Node 数组）。当链表长度 ≥ 8 且数组容量 ≥ 64 时，链表转为红黑树，最坏查询复杂度优化至 O(log n)。
- 插入方式（解决死循环关键）
- JDK 1.7：采用头插法。扩容时链表元素顺序反转，多线程并发扩容易形成环形链表，导致 `get` 操作死循环（CPU 100%）。
- JDK 1.8：采用尾插法。扩容时保持原链表顺序，彻底解决了环形链表死循环问题（但仍非线程安全，存在数据覆盖风险）。
- 扩容迁移逻辑
- JDK 1.7：需重新计算每个元素的 hash 值和数组下标，效率较低。
- JDK 1.8：利用 `hash & oldCap` 位运算判断元素位置。结果为 0 留在原下标，结果为 1 移至 `原下标 + 旧容量`，无需重算 hash，迁移效率大幅提升。
- 初始化时机
- JDK 1.7：构造方法中直接初始化数组（默认容量 16）。
- JDK 1.8：懒加载，第一次 `put` 时才初始化数组，节省内存。
红黑树转换阈值（JDK 1.8 特有）
- 树化条件：链表长度 ≥ 8 且 数组容量 ≥ 64（若容量不足 64，优先扩容而非树化）。
- 退化条件：红黑树节点数 ≤ 6 时，退化为链表。
- 设计原因：基于泊松分布，链表长度达 8 的概率极低（约千万分之六），设置 6-8 缓冲区间避免频繁转换开销。
总结建议
JDK 1.8 在保持兼容性的同时，通过红黑树兜底解决了长链表性能问题，通过尾插法消除了并发死循环隐患。生产环境若涉及高并发读写，无论哪个版本均建议使用 `ConcurrentHashMap` 替代 `HashMap`。
二、HashMap的put流程
HashMap 的 put 流程在 JDK 1.7 和 JDK 1.8 中存在显著差异，主要体现在数据结构优化、插入方式及扩容时机上。以下是基于主流 JDK 1.8 版本的详细流程解析，并对比 JDK 1.7 的关键区别。
一、JDK 1.8 HashMap put() 核心流程
JDK 1.8 的 put 操作底层调用的是 putVal() 方法，其执行逻辑可以概括为以下 5 个关键步骤：
1. 初始化检查与哈希计算
- 懒加载初始化：如果底层数组 table 为 null 或长度为 0，首先调用 resize() 方法进行初始化（默认容量 16）。
- 计算 Hash 值：通过 hash(key) 方法计算键的哈希值。该方法将 key 的 hashCode() 高 16 位与低 16 位进行异或运算，目的是让高位也参与索引计算，减少哈希冲突。
- 确定数组下标：使用公式 (n - 1) & hash 计算元素在数组中的索引位置 i（其中 n 为数组长度）。
2. 判断桶（Bucket）状态
根据计算出的下标 i，检查 table[i] 的情况：
- 情况 A：桶为空
- 直接在该位置创建一个新的节点（Node）并插入。这是最理想的情况，时间复杂度为 O(1)。
- 情况 B：桶不为空（发生哈希冲突）
- 进入冲突处理逻辑，需进一步判断首节点类型。
3. 处理哈希冲突
当 table[i] 已有元素时，按以下顺序处理：
- 检查首节点：如果首节点的 hash 值和 key 与待插入元素相同（通过 == 或 equals() 判断），则直接覆盖旧值，并返回旧值。
- 判断是否为红黑树：如果首节点是 TreeNode 类型，说明该桶已树化，调用 putTreeVal() 方法将元素插入红黑树中。
- 遍历链表：如果首节点是普通链表节点：
- 遍历链表，查找是否存在相同的 key。若存在，覆盖旧值。
- 若遍历到链表末尾仍未找到相同 key，则采用尾插法将新节点追加到链表尾部。
4. 链表转红黑树（树化）
在链表插入新节点后，检查链表长度：
- 如果链表长度 ≥ 8，且数组容量 ≥ 64，则将链表转换为红黑树，以提升后续查询效率（从 O(n) 优化至 O(log n)）。
- 注：若数组容量 < 64，即使链表长度达到 8，也会优先选择扩容而非树化。
5. 扩容检查
- 插入成功后，检查当前元素总数 size 是否超过阈值 threshold（容量 × 负载因子，默认 0.75）。
- 若超过阈值，调用 resize() 方法进行扩容（容量变为原来的 2 倍），并重新分布元素。
二、JDK 1.7 vs JDK 1.8 put 流程关键区别
| 特性 | JDK 1.7 | JDK 1.8 |
|---|---|---|
| 底层结构 | 数组 + 单向链表 | 数组 + 链表 + 红黑树 |
| 插入方式 | 头插法 新元素插在链表头部，效率高但扩容时会反转链表顺序。 | 尾插法 新元素插在链表尾部，保持插入顺序，避免并发扩容死循环。 |
| 扩容时机 | 插入前判断 先判断是否扩容，再执行插入。若插入位置为空但 size 达标，可能触发无效扩容。 | 插入后判断 先执行插入，再判断是否扩容。逻辑更清晰，避免无效扩容。 |
| Hash 算法 | 多次移位和异或，针对 String 有特殊优化。 | 高位异或h ^ (h >>> 16)，简化计算，使高位特征参与低位运算，分布更均匀。 |
| 冲突解决 | 仅链表，极端情况下查询退化为 O(n)。 | 链表长度 ≥8 且容量 ≥64 时转为红黑树，查询优化为 O(log n)。 |
| Null Key 处理 | 专门调用putForNullKey，固定存放在table。 | 统一在putVal中处理，null 的 hash 值为 0，存放在table。 |
三、常见面试考点解析
1.为什么 JDK 1.8 改用尾插法？
- JDK 1.7 的头插法在多线程并发扩容时，可能导致链表形成环形结构，进而引发 get 操作死循环（CPU 100%）。JDK 1.8 的尾插法保证了扩容前后链表顺序一致，彻底解决了此问题（但 HashMap 依然非线程安全，数据覆盖风险仍存在）。
2.为什么红黑树转换阈值是 8？
- 根据泊松分布统计，在哈希值随机分布的情况下，链表长度达到 8 的概率极低（约千万分之六）。设置 8 作为阈值，既避免了频繁树化带来的性能开销（红黑树节点占用空间是普通节点的两倍），又能有效应对极端哈希冲突场景。
3.扩容时元素如何迁移？（JDK 1.8 优化）
- JDK 1.7 需要重新计算每个元素的 hash 值和索引。
- JDK 1.8 利用 hash & oldCap 判断：
- 结果为 0：元素留在原索引位置。
- 结果为 1：元素移至 原索引 + 旧容量 的位置。
- 这种位运算方式无需重新计算 hash，大幅提升了扩容效率。
4.总结
JDK 1.8 的 put 流程通过引入红黑树和尾插法，在保持高效插入的同时，显著提升了极端冲突下的查询性能，并消除了并发扩容的死循环隐患。在实际开发中，若涉及高并发场景，仍建议使用 ConcurrentHashMap。
三、HashMap与ConcurrentHashMap
HashMap和ConcurrentHashMap的核心区别集中在线程安全实现、锁机制、细节行为和适用场景上。
一、核心基础差异
| 对比维度 | HashMap | ConcurrentHashMap |
|---|---|---|
| 线程安全性 | 非线程安全，多线程并发修改时易出现数据覆盖、JDK1.7下扩容死循环问题，需外部手动加锁同步 | 专为高并发设计的线程安全实现，内置并发控制机制，无需额外同步即可保证多线程读写的数据一致性 |
| 底层数据结构 | JDK1.8后采用「数组+链表+红黑树」结构，链表长度≥8且数组容量≥64时树化 | JDK1.8后采用和HashMap一致的「数组+链表+红黑树」结构，保留树化、反树化的性能优化逻辑 |
| 锁机制（JDK1.8） | 无任何内置锁，完全依赖单线程环境保证操作安全 | 采用CAS+synchronized实现细粒度锁：插入空桶用CAS无锁写入，哈希冲突后仅锁住当前链表头/红黑树根节点，锁粒度细化到单个哈希桶，支持多线程并发操作不同桶的数据，性能远高于全局锁 |
| 锁机制（JDK1.7） | 无锁 | 采用Segment分段锁，将整个哈希表划分为多个独立分段，每个分段持有一把ReentrantLock，多线程可同时访问不同分段，并发度由分段数决定 |
二、关键细节行为差异
- Null值处理
- HashMap：宽松支持，允许存在1个null键和多个null值，单线程场景下使用灵活。
- ConcurrentHashMap：严格禁止null键和null值，插入null会直接抛出异常，避免并发场景下无法区分「键不存在」和「值本身为null」的歧义问题。
- 迭代器特性
- HashMap：迭代器为快速失败（Fail-Fast），遍历过程中检测到结构修改会立即抛出ConcurrentModificationException异常。
- ConcurrentHashMap：迭代器为弱一致性，遍历过程中允许其他线程修改数据，不会抛出异常，适配高并发下的迭代场景。
3. 扩容与统计优化
- HashMap：单线程执行扩容迁移，size()方法直接返回元素总数，统计简单无额外优化。
- ConcurrentHashMap：支持多线程并发协助扩容，大幅提升大表扩容的迁移效率；size()方法通过baseCount+CounterCell分散统计元素数量，无需加全局锁即可在高并发下兼顾统计性能。
三、适用场景选择
- 单线程场景：优先选择HashMap，无同步开销，单线程读写性能最优，适合局部变量、只读缓存等场景。
- 高并发多线程场景：必须选择ConcurrentHashMap，适配全局缓存、计数器等频繁读写的场景，在保证线程安全的同时提供远高于同步包装HashMap的并发性能。
