HashMap/ConcurrentHashMap 底层实现

HashMap 和 ConcurrentHashMap 是 Java 中最常用的两种 Map 实现它们在底层结构和线程安全策略上有显著差异。简单来说HashMap 是非线程安全的而 ConcurrentHashMap 是线程安全的并且其并发控制策略在不同 JDK 版本中有很大变化。下面我们从底层数据结构和线程安全实现两个方面来拆解。 底层数据结构数组、链表与红黑树它们的底层本质上都是一种哈希表结构用于存储键值对。解决哈希冲突的核心方法是链地址法也叫拉链法即数组每个位置是一个“桶”当多个键映射到同一个桶时会形成一个链表。JDK 1.7 的 HashMap / ConcurrentHashMap内部是一个Entry数组每个Entry对象是链表的节点。发生哈希冲突时新节点会通过头插法插入链表头部。ConcurrentHashMap在此基础上在数组和链表之上又引入了Segment数组将数据分段管理。JDK 1.8 及之后的 HashMap / ConcurrentHashMap结构演变为数组 链表 红黑树。当链表长度超过阈值默认为8且数组总容量大于等于64时链表会转换为红黑树将查找时间复杂度从 O(n) 优化到 O(log n)以应对大量哈希冲突的场景。新节点插入方式改为尾插法避免了并发扩容时可能产生的死循环问题。ConcurrentHashMap的数据结构与 HashMap 保持高度一致但节点类型和并发控制细节不同。 线程安全实现从分段锁到 CAS Synchronized这是 ConcurrentHashMap 与 HashMap 的核心区别也是其实现并发高性能的关键。特性HashMap (所有版本)ConcurrentHashMap (JDK 1.7)ConcurrentHashMap (JDK 1.8)线程安全否。多线程并发修改会引发数据错乱、死循环等问题。是。采用分段锁机制。是。采用CAS synchronized机制。锁粒度无锁不涉及。粗粒度。Segment数组中的每个Segment独立持有一把锁继承自ReentrantLock一个锁保护该Segment下的所有桶。细粒度。锁只作用于单个桶的头节点Node或树根节点。只有发生哈希冲突、操作同一个桶的线程才会竞争锁。并发性能单线程下性能最高。理论上最大支持Segment数量的并发写操作比全表锁的HashTable强但两次哈希寻址有一定开销。锁粒度极细并发性能在大多数场景下优于 JDK 1.7 版本接近单线程的 HashMap。对 null 的支持允许一个null键和多个null值。不允许null键或值。若传入null会抛出NullPointerException。不允许null键或值。 核心机制补充1. 哈希寻址优化计算数组索引时两者都用了类似的优化手段对键的hashCode()进行高低位异或(h key.hashCode()) ^ (h 16)让高位也参与索引计算使数据分布更均匀。然后通过(table.length - 1) hash获取桶下标前提是数组长度必须是2的幂。2. 扩容机制HashMap当存储的键值对数量 容量 * 负载因子(默认0.75)时触发扩容新容量为旧容量的2倍所有元素需重新计算索引rehash。ConcurrentHashMap (JDK 1.7)Segment内部扩容不影响其他Segment。ConcurrentHashMap (JDK 1.8)支持多线程协同扩容每个线程负责一部分旧桶的数据迁移提高扩容效率。 总结如何选择单线程环境直接使用HashMap它简单且性能最优。多线程环境务必使用ConcurrentHashMap。它比使用Collections.synchronizedMap()包装的 HashMap 或古老的HashTable有更高的并发性能且迭代器是弱一致性的不会抛出ConcurrentModificationException。具体采用 JDK 1.7 还是 1.8 的实现取决于你的 Java 版本1.8 版本的设计更优。cas 和 synchronized 是怎么用的这个问题问得很细。在ConcurrentHashMap的源码里CAS乐观锁和synchronized悲观锁不是替代关系而是分工合作的关系。它们被用在不同的操作阶段目的都是为了在保证线程安全的同时把性能开销降到最低。简单来说核心策略是先用 CAS 尝试无锁操作如果失败说明有竞争再视情况用 synchronized 锁住单个桶进行更稳重的操作。我们可以把它的put方法流程拆开来看这是最典型的应用场景。场景一初始化数组用 CAS 保证只初始化一次当ConcurrentHashMap刚被创建时内部的哈希表数组table是空的。第一个插入元素的线程需要触发数组初始化。用的什么CAS怎么用的多个线程可能同时检测到数组未初始化都会去执行初始化。为了避免重复初始化源码里会使用 CAS 来修改一个名为sizeCtl的控制变量。谁用 CAS 成功地把sizeCtl从-1或默认值改为了一个标识状态谁就获得了执行初始化的资格其他线程看到状态不对就会主动让出 CPUyield()或自旋等待。这段代码的核心意图是用轻量级的 CAS 替代重量级的锁快速完成创建动作避免线程阻塞。场景二定位到空桶时插入用 CAS 直接放数据当我们计算出一个键的哈希值并定位到数组的某个下标后如果发现这个下标位置即“桶”是空的没有任何元素。用的什么CAS怎么用的此时不需要加锁。线程会创建一个新的Node节点然后使用CAS操作底层是Unsafe.compareAndSwapObject尝试将这个新节点直接设置到数组的空位置上。结果如果 CAS 成功说明在当前线程设置时没有其他线程抢先一步放入数据插入完成。如果 CAS 失败说明就在这个瞬间另一个线程也发现了这个空桶并抢先放入了数据。当前线程不会加锁而是会重新循环spin再次判断该桶的状态然后走接下来的逻辑比如进入链表追加。这段代码的核心意图是在完全没有哈希冲突的情况下用一次 CAS 原子操作就完成了插入性能极高几乎和单线程的 HashMap 一样快。场景三桶非空且存在哈希冲突用 synchronized 锁住桶头节点如果定位到的桶已经有元素了即发生了哈希冲突无论是形成链表还是红黑树此时涉及对链表或树结构的修改如插入节点、修改节点、删除节点。由于结构操作逻辑复杂无法用一次简单的 CAS 搞定。用的什么synchronized怎么用的代码会进入synchronized代码块锁的对象就是这个桶的“头节点”数组上的第一个 Node 或 TreeNode。javasynchronized (f) { // f 就是桶的头节点 // 再次检查头节点是否被修改 (双重检查) // 遍历链表或红黑树进行 put 或 replace 操作 }关键细节锁粒度极细锁的是桶的头节点而不是整个数组或 Segment。因此多线程操作不同桶时完全互不干扰。锁升级synchronized在 JVM 层面有偏向锁、轻量级锁、重量级锁的升级过程。如果该桶只有一个线程操作它甚至只是轻量级锁类似自旋开销很小只有在多线程激烈竞争同一个桶时才会升级为重量级的互斥锁让线程进入等待队列。场景四协助扩容时的数据迁移CAS synchronized 结合在扩容时需要将旧数组的元素迁移到新数组。这是一个复杂的多线程协作任务。任务分配用 CAS使用 CAS 来“抢占”迁移任务的索引transferIndex每个线程用 CAS 不断往下分配自己负责的一段区间确保任务不被重复领取。数据迁移用 synchronized当真正迁移某个桶的数据时为了防止在迁移过程中该桶被修改会锁住这个桶的头节点synchronized (f)保证迁移时数据的一致性。 总结一张表帮你更清晰地理解操作阶段使用技术锁粒度/作用范围核心原因初始化数组CAS全局变量 (sizeCtl)只需要保证只初始化一次无复杂逻辑CAS 足够且轻量。插入到空桶CAS单个数组槽位 (table[i])原子操作简单直接替换即可无需阻塞线程性能最高。插入到非空桶synchronized单个桶的头节点 (Node)涉及链表/树的遍历、插入和调整逻辑复杂需要保证操作的原子性和可见性。执行扩容任务CAS全局索引 (transferIndex)多个线程争抢任务区间用 CAS 分配高效无阻塞。迁移桶内数据synchronized单个桶的头节点保证迁移期间该桶数据不被修改确保数据完整复制到新数组。最后想补充一点这种“先 CAS后 synchronized”的组合设计其实是现代并发容器的一种经典范式。它充分利用了 CAS 在低竞争下的高性能优势同时又用synchronized来兜底处理复杂逻辑和多线程激烈竞争的场景避免了实现复杂且容易出问题的“自旋CAS”重试机制。如果你还想了解 JDK 1.7 中ReentrantLock分段锁和 1.8 中synchronized锁的具体性能差异或者想看get方法是如何实现无锁读取的我们可以继续深入探讨。