今日任务时间动作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.7JDK 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与ConcurrentHashMapHashMap和ConcurrentHashMap的核心区别集中在线程安全实现、锁机制、细节行为和适用场景上。一、核心基础差异对比维度HashMapConcurrentHashMap线程安全性非线程安全多线程并发修改时易出现数据覆盖、JDK1.7下扩容死循环问题需外部手动加锁同步专为高并发设计的线程安全实现内置并发控制机制无需额外同步即可保证多线程读写的数据一致性底层数据结构JDK1.8后采用「数组链表红黑树」结构链表长度≥8且数组容量≥64时树化JDK1.8后采用和HashMap一致的「数组链表红黑树」结构保留树化、反树化的性能优化逻辑锁机制JDK1.8无任何内置锁完全依赖单线程环境保证操作安全采用CASsynchronized实现细粒度锁插入空桶用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()方法通过baseCountCounterCell分散统计元素数量无需加全局锁即可在高并发下兼顾统计性能。三、适用场景选择单线程场景优先选择HashMap无同步开销单线程读写性能最优适合局部变量、只读缓存等场景。高并发多线程场景必须选择ConcurrentHashMap适配全局缓存、计数器等频繁读写的场景在保证线程安全的同时提供远高于同步包装HashMap的并发性能。
