文日小栈

1. 完整回答

HashMap 和 ConcurrentHashMap 都是 Java 中基于哈希表实现的键值对集合，主要区别是线程安全性和并发控制机制。

HashMap 适用于单线程环境，本身不保证线程安全；ConcurrentHashMap 专门用于多线程共享数据的场景，能够保证单次操作的线程安全，同时尽量减少锁竞争。

从底层结构来看，JDK 8 及之后的主流实现都采用数组 + 链表 + 红黑树。首先通过 Key 的哈希值定位数组中的桶，如果发生哈希冲突，就通过链表或者红黑树保存多个节点。正常情况下，查询和插入的平均时间复杂度都是 O(1)，红黑树主要用于改善严重哈希冲突时的查询性能。

HashMap 的默认初始容量是 16，默认负载因子是 0.75，元素数量超过扩容阈值后，通常会扩容为原来的两倍。由于内部没有并发同步机制，多线程同时修改时可能出现数据丢失或者结构异常。

ConcurrentHashMap 在 JDK 8 中采用 CAS + synchronized + volatile 实现并发控制。空桶插入优先使用 CAS，发生哈希冲突时对对应的桶进行同步，读取操作通常不需要加锁，扩容时还支持多个线程协助数据迁移。

另外，ConcurrentHashMap 不允许 null 键和值，支持 putIfAbsent、compute 等原子操作，但多个独立操作组合起来仍然需要考虑竞态条件。

2. 核心原理与关键概念

2.1 HashMap 的底层原理

核心数据结构：数组 + 链表 + 红黑树。

put 操作流程：

计算 Key 的哈希值 → 定位数组下标 → 判断桶是否为空 → 插入或更新节点 → 必要时树化或扩容。

计算哈希值：通过 hashCode() 获取哈希值，并进行扰动处理，让高位信息参与索引计算。
定位桶位置：通过 (n - 1) & hash 计算数组下标，其中 n 是数组长度。
处理哈希冲突：如果桶为空，直接插入；如果已有节点，通过哈希值和 equals() 判断 Key 是否相同，相同则更新，否则继续查找或插入。
链表树化：当链表过长时会触发树化检查，树化阈值为 8，同时要求数组容量至少为 64；容量不足时优先扩容。
扩容：元素数量超过阈值后，通常将数组容量扩大一倍，并重新分配节点位置。

get 操作流程：

计算哈希值 → 定位桶 → 比较 Key → 遍历链表或搜索红黑树 → 返回对应的 Value。

哈希分布均匀时，查询效率接近 O(1)；大量元素集中到同一个桶时，链表查询可能退化为 O(n)，红黑树能够改善这种情况。

2.2 ConcurrentHashMap 的底层原理

JDK 8 之后，ConcurrentHashMap 的核心机制是 CAS + synchronized + volatile + 多线程协助扩容。

put 操作流程：

计算哈希值 → 定位桶 → 判断桶状态 → CAS 插入或加锁更新 → 更新元素计数 → 必要时参与扩容。

空桶插入：使用 CAS 尝试写入新节点，成功后无需获取互斥锁。
非空桶写入：通过 synchronized 对桶头节点进行同步，在桶内完成链表或红黑树的更新。
遇到扩容：如果发现对应桶已经迁移，线程可以协助完成剩余的数据迁移。
更新计数：通过基础计数和分散计数单元减少并发更新时的竞争。

get 操作流程：

计算哈希值 → 定位桶 → 读取节点 → 遍历链表或红黑树 → 返回结果。

读取通常无需加锁，主要依赖 volatile 和相应的原子访问机制保证节点发布与数据可见性。

扩容流程：

触发扩容 → 创建新数组 → 多线程分工迁移桶 → 设置迁移标记 → 完成新旧数组切换。

迁移标记节点（ForwardingNode）用于引导其他线程访问新数组，也让后续写入线程能够参与扩容。

2.3 关键概念

概念	含义与作用
哈希冲突	不同 Key 落入同一个桶，通过链表或红黑树解决
负载因子	控制元素密度与扩容时机，HashMap 默认是 0.75
CAS	比较并交换，通过原子操作减少简单写入的锁开销
synchronized	保证桶内多个节点修改操作的互斥性
volatile	提供必要的可见性和内存有序性保证，支持并发读取

3. 高频面试追问

3.1 为什么 HashMap 线程不安全？

HashMap 的内部数据修改没有并发同步保护，多个线程同时执行写操作时，可能出现数据覆盖、更新丢失以及扩容期间的结构异常。

例如，两个线程同时发现某个桶为空，都准备插入节点，最后一个线程的写入可能覆盖另一个线程的结果。

另外，HashMap 的扩容涉及数组替换和节点迁移，并发执行时可能出现数据丢失。

JDK 7 的 HashMap 曾存在并发扩容导致链表成环的典型问题。JDK 8 调整了链表迁移方式，但仍然没有提供线程安全保证。

因此，只要存在多个线程并发修改共享 HashMap 的情况，就需要额外同步，或者选择 ConcurrentHashMap。

3.2 HashMap 为什么使用 2 的幂作为数组容量？

主要是为了提高索引计算效率，并简化扩容后的节点迁移。

当数组长度 n 是 2 的幂时，可以使用 (n - 1) & hash 计算桶下标，效果相当于对数组长度取模。

此外，数组容量扩大两倍后，原来某个桶中的节点只会留在原下标，或者移动到“原下标 + 旧容量”的位置。

这样就能通过哈希值的特定位判断节点的新位置，减少重新定位的计算开销。

继续追问：hashCode 相同的两个 Key 一定相等吗？

不一定。哈希值相同只代表发生了哈希冲突，还需要通过 equals() 判断。

反过来，两个通过 equals() 判断相等的 Key，必须具有相同的 hashCode()。如果自定义对象违反这个约定，HashMap 可能无法正确查找对应元素。

3.3 HashMap 为什么引入红黑树？什么时候树化？

引入红黑树主要是为了降低严重哈希冲突带来的性能损耗。

在 JDK 8 之前，桶内主要使用链表保存冲突节点，如果大量元素落入同一个桶，查找时间复杂度可能退化为 O(n)。

JDK 8 引入红黑树后，对于能够有效排序的冲突节点，查询通常可以改善到 O(log n)。

树化涉及三个关键阈值：

8：链表树化的触发阈值。
64：允许树化的最小数组容量。
6：树节点数量减少时，退化为链表所涉及的阈值。

之所以要求数组容量至少为 64，是因为容量较小时，哈希冲突可能来自数组空间不足，此时扩容通常比维护红黑树更合适。

3.4 HashMap 和 ConcurrentHashMap 的扩容有什么区别？

两者通常都会将数组容量扩大一倍，核心区别是扩容过程是否支持线程安全的协作。

HashMap 扩容时，会创建新数组，然后依次迁移旧数组中的节点。由于数组长度是 2 的幂，可以根据哈希值判断节点留在原位置，还是移动到偏移了旧容量的位置。

ConcurrentHashMap 则支持多个线程协助扩容。

当一个线程启动扩容后，其他线程如果发现迁移正在进行，可以参与迁移不同范围的桶。已经迁移完成的桶会设置特殊标记，帮助后续线程定位新数组。

这种设计能够分摊扩容工作，减少单个线程承担全部迁移任务带来的延迟，同时保证迁移期间的数据访问安全。

3.5 JDK 7 和 JDK 8 的 ConcurrentHashMap 有什么区别？

最大的区别是并发锁的粒度和底层组织方式发生了变化。

JDK 7 使用分段锁机制，底层通过 Segment 将数据划分成多个部分，每个 Segment 使用 ReentrantLock 控制写入。不同 Segment 可以并发修改，但同一个 Segment 内的写入需要竞争同一把锁。

JDK 8 移除了 Segment 结构，改用数组、链表和红黑树，并结合 CAS 与 synchronized 控制写入。

当桶为空时使用 CAS；当桶内存在节点时，主要锁住对应桶的头节点。

这样可以缩小锁的影响范围，使不同桶的更新更容易并发执行。

另外，JDK 8 之后的 concurrencyLevel 主要作为初始化容量的参考参数，不再对应固定数量的分段锁。

3.6 ConcurrentHashMap 的 get 为什么不需要加锁？

因为它通过内存可见性机制和安全的节点发布方式，保证读取线程能够正确访问已经发布的数据。

ConcurrentHashMap 中的节点值、后继节点等关键字段使用 volatile，并通过具有相应内存语义的方式访问桶节点。

写入线程完成节点发布后，读取线程能够按照内存可见性规则观察到已经完成的更新。

所以，get 通常只需要定位桶，再遍历链表或者红黑树，就可以返回结果，不必获取写入时使用的互斥锁。

但这里保证的是单次读取的并发语义。如果读取过程中其他线程正在修改数据，多次 get 之间仍然可能观察到不同状态。

3.7 为什么 ConcurrentHashMap 不允许 null？

主要是为了消除并发读取时的语义歧义。

在 HashMap 中，get(key) 返回 null，可能有两种情况：

Key 不存在。
Key 存在，但对应的 Value 是 null。

单线程下，可以通过 containsKey() 进一步判断。

但在并发环境中，调用 get() 和 containsKey() 之间，其他线程可能已经修改了映射关系，因此两次调用无法保证观察到同一个状态。

ConcurrentHashMap 禁止 null 键和值后，get(key) 返回 null 就可以明确表示当前没有对应映射。

这也方便其并发计算和批量操作使用 null 表示结果缺失。

3.8 ConcurrentHashMap 能保证所有操作都是原子性的吗？

ConcurrentHashMap 能保证规定的单次操作具有相应的线程安全和原子性语义，但多个独立操作组合起来，并不会自动形成一个原子操作。

例如，先通过 get 读取计数，再加一并 put 回去，两个线程可能读到相同的旧值，最终造成更新丢失。

对于这种场景，可以使用：

putIfAbsent()：保证不存在时才插入。
compute()：原子地根据旧值计算新值。
merge()：原子地合并新旧值。

如果是高并发热点计数，还可以使用 ConcurrentHashMap<K, LongAdder>，减少频繁累加时的竞争。

继续追问：computeIfAbsent 适合执行耗时操作吗？

通常不适合。ConcurrentHashMap 的 computeIfAbsent() 会对对应键的计算与插入过程提供原子性保证，计算期间可能阻塞其他更新操作。

因此，计算函数应该尽量简短，并避免在函数内部修改同一个 Map。涉及远程调用、慢查询等耗时任务时，还需要专门设计并发加载机制。

3.9 HashMap 和 ConcurrentHashMap 的迭代器有什么区别？

HashMap 的迭代器采用 fail-fast（快速失败）机制，ConcurrentHashMap 的迭代器采用弱一致性机制。

HashMap 在创建迭代器后，如果集合发生未经迭代器自身操作的结构性修改，通常会抛出 ConcurrentModificationException。

它主要通过修改次数检测结构变化，但这个异常只是尽力检测，并不保证每次并发修改都会被发现。

ConcurrentHashMap 允许遍历与修改同时进行，迭代器不会因为并发结构修改而抛出这个异常。

不过，它也不提供某个时刻的完整快照，遍历结果可能包含部分新修改的数据，也可能看不到部分并发更新。

因此，如果业务要求严格一致的完整快照，还需要额外的一致性控制。

3.10 实际项目中如何选择 HashMap 和 ConcurrentHashMap？

主要根据数据是否在线程之间共享，以及是否存在并发修改来选择。

如果数据只在单个方法或单个线程内部使用，HashMap 通常更简单，开销也更低。

如果多个线程共享用户状态、缓存映射或者任务执行状态，并且存在并发读写，更适合选择 ConcurrentHashMap。

不过，还需要注意两个边界。

第一，ConcurrentHashMap 的 size() 在并发修改期间反映的是瞬时计数，不适合直接作为要求严格一致性的业务判断依据。

第二，ConcurrentHashMap 只保证 Map 自身操作的并发安全。如果需要跨多个 Key 维护一致性，就需要额外同步或者重新设计数据更新方式。

继续追问：ConcurrentHashMap 中存放的对象也是线程安全的吗？

不一定。

ConcurrentHashMap 能安全地管理键值映射关系，但如果 Value 本身是一个可变对象，例如 ArrayList，多个线程同时修改这个对象时，仍然可能出现并发问题。

这种情况下，需要使用线程安全的 Value 类型，或者额外保护对象内部的修改操作。

4. 易混淆概念对比

4.1 HashMap 和 ConcurrentHashMap

对比维度	HashMap	ConcurrentHashMap
线程安全	不保证	保证单次操作的线程安全
底层结构	数组 + 链表 + 红黑树	数组 + 链表 + 红黑树
并发控制	无内置同步	CAS + synchronized + volatile
null 键和值	允许	不允许
读取操作	无并发安全保证	通常无锁
扩容	普通节点迁移	支持多线程协助迁移
迭代器	快速失败	弱一致性
适用场景	局部数据、单线程处理	多线程共享映射、并发缓存

4.2 CAS、synchronized 和 volatile

机制	核心作用	ConcurrentHashMap 中的应用
CAS	通过原子比较更新数据	空桶插入、部分状态更新
synchronized	保证临界区互斥执行	非空桶的节点修改
volatile	保证可见性及相关有序性	支持安全发布和读取节点

三者相互配合，在保证并发安全的同时减少不必要的锁竞争。

4.3 putIfAbsent、computeIfAbsent 和 compute

方法	核心行为	适用场景
`putIfAbsent`	Key 不存在时插入指定值	并发条件插入
`computeIfAbsent`	Key 不存在时计算并插入值	懒加载、初始化
`compute`	根据当前值计算新映射	计数更新、状态变更

对于 ConcurrentHashMap，这些方法可以提供对应操作的原子性保证。其中，计算函数应保持简短，避免修改同一个 Map。

4.4 快速失败与弱一致性

对比维度	快速失败（fail-fast）	弱一致性
典型实现	HashMap	ConcurrentHashMap
并发修改	可能抛出异常	允许并发遍历和修改
数据一致性	不支持无同步并发遍历	不保证完整快照
主要特点	尽早发现结构性修改	支持持续并发访问

5. 总结

HashMap 和 ConcurrentHashMap 都是基于哈希表的键值对集合，通过数组定位桶，再利用链表或红黑树解决哈希冲突，正常情况下查询效率接近 O(1)。HashMap 结构简单，适合单线程环境，但不保证并发安全。ConcurrentHashMap 在 JDK 8 之后通过 CAS、synchronized 和 volatile 配合实现线程安全，读取通常无需加锁，写入控制在桶级别，扩容时还支持多线程协作。两者最核心的区别是并发控制机制。另外，ConcurrentHashMap 的线程安全主要针对集合自身的操作，多个操作组合以及 Value 对象内部的修改，仍然需要根据业务保证一致性。