ConcurrentHashMap ——put + get

在 Java 并发编程中ConcurrentHashMap是当之无愧的明星容器。它既要在多线程环境下保证线程安全又要追求接近HashMap的高性能。本文将带你深入剖析ConcurrentHashMap的 put 和 get 流程从源码视角解读其精妙设计理解它如何通过无锁读、CAS 原子操作、细粒度锁以及多线程协助扩容实现了并发与性能的完美平衡。一、从 Hashtable 到 ConcurrentHashMap在 Java 早期Hashtable是唯一的线程安全哈希表但它对所有方法都加synchronized整个表被一把大锁保护。高并发下这把锁成为严重的性能瓶颈——任何时刻只有一个线程能访问。而HashMap虽然性能高却非线程安全。于是Java 并发包推出了ConcurrentHashMap目标是细粒度锁将锁的粒度从整个表缩小到每个桶bucket。无锁读读操作不加锁依靠volatile保证可见性。CAS 无锁更新对于简单操作如空桶插入、计数器更新使用乐观锁 CAS 替代重量级锁。多线程协助扩容将耗时的扩容任务拆解让多个线程共同完成减少单次扩容的停顿时间。二、核心数据结构Java 8Java 8 的ConcurrentHashMap彻底重构放弃了 Java 7 的分段锁Segment采用了更精妙的数组 链表 红黑树结构NodeK,V[] table哈希桶数组用volatile修饰保证数组引用对所有线程可见。Node节点包含hash、key、valvolatile和nextvolatile。当链表长度超过 8 且数组长度 ≥ 64 时链表会转换为红黑树TreeNode查询复杂度从 O(n) 降到 O(log n)。ForwardingNode扩容时的特殊节点用于指向新数组标记该桶已被迁移。三、put 流程详解并发写入的精妙设计ConcurrentHashMap的put方法既要处理普通插入又要应对并发竞争、扩容等复杂场景。下面我们逐步拆解其核心流程。1. 参数校验与哈希扰动public V put(K key, V value) { return putVal(key, value, false); }首先ConcurrentHashMap不允许 key 或 value 为 null一旦检测到 null直接抛出NullPointerException。对 key 的hashCode()进行二次扰动spread()方法目的是让高位也参与运算减少哈希冲突使数据分布更均匀。static final int spread(int h) { return (h ^ (h 16)) HASH_BITS; }2. 计算桶下标通过(n - 1) hash计算桶下标其中n是数组长度总是 2 的幂次。这个操作等价于取模但效率更高。3. 空桶插入CAS 无锁操作如果定位到的桶为空则使用CAS原子地插入新节点。这是无锁操作避免了加锁开销if ((f tabAt(tab, i (n - 1) hash)) null) { if (casTabAt(tab, i, null, new NodeK,V(hash, key, value, null))) break; // 插入成功跳出循环 }如果 CAS 失败说明有其他线程抢先插入了则进入下一次自旋重试。4. 正在扩容协助迁移如果桶的头节点是ForwardingNode其hash值为MOVED说明当前数组正在扩容。此时当前线程不会阻塞等待而是调用helpTransfer()方法主动加入扩容任务帮助迁移其他桶中的数据再继续自己的put操作。这种设计将扩容的压力分散到多个写线程大大缩短了整体扩容时间。5. 正常插入细粒度锁如果桶不为空且不是ForwardingNode就对桶的头节点加synchronized锁锁对象就是这个节点。注意这里只锁住了当前桶其他桶的操作完全不受影响实现了细粒度并发控制。加锁后再次检查头节点是否被修改双重检查然后根据节点类型进行插入链表遍历遍历链表如果找到相同 key则覆盖 value根据onlyIfAbsent参数决定否则在链表尾部插入新节点Java 8 采用尾插法避免并发下链表环的问题。红黑树如果是TreeBin节点则调用红黑树的插入方法同样在锁保护下进行。6. 树化判断插入完成后如果当前桶的链表长度 ≥ 8会触发树化判断如果数组长度 64优先扩容数组tryPresize因为较短的数组容易导致哈希冲突扩容可以更有效地解决冲突。如果数组长度 ≥ 64则将链表转换为红黑树将查询复杂度从 O(n) 降到 O(log n)。7. 更新计数与扩容触发最后调用addCount()更新元素总数。该方法使用LongAdder思想将计数分散到baseCount和CounterCell数组中通过 CAS 原子更新减少高并发下的竞争。同时addCount()会检查当前元素数量是否超过sizeCtl扩容阈值若达到则触发扩容流程。四、get 流程全程无锁性能接近 HashMapConcurrentHashMap的get操作是完全无锁的这是其高并发读性能的核心。整个查询过程仅依赖volatile保证可见性。public V get(Object key) { NodeK,V[] tab; NodeK,V e, p; int n, eh; K ek; int h spread(key.hashCode()); if ((tab table) ! null (n tab.length) 0 (e tabAt(tab, (n - 1) h)) ! null) { // 1. 检查头节点 if ((eh e.hash) h) { if ((ek e.key) key || (ek ! null key.equals(ek))) return e.val; } // 2. 特殊节点红黑树或扩容转发节点 else if (eh 0) return (p e.find(h, key)) ! null ? p.val : null; // 3. 普通链表遍历 while ((e e.next) ! null) { if (e.hash h ((ek e.key) key || (ek ! null key.equals(ek)))) return e.val; } } return null; }步骤解析计算桶下标通过tabAt获取桶头节点volatile读保证可见性。检查头节点如果头节点的 key 匹配直接返回 value。特殊节点如果头节点的 hash 小于 0表示是红黑树节点或扩容转发节点调用其find方法查找。红黑树的查找遵循二叉搜索树规则从根开始比较哈希值小于走左子树大于走右子树哈希相等再用equals判断扩容转发节点则会去新数组查找。链表遍历否则按链表顺序遍历找到匹配的 key 则返回 value否则返回 null。整个过程没有加任何锁只依赖volatile保证读到的值是最新的。即使有并发写volatile也能保证修改对读线程可见因此读性能几乎与HashMap持平。五、其他关键机制1. 计数机制LongAdder 思想ConcurrentHashMap的size()方法需要实时返回元素个数。高并发下使用AtomicLong会导致大量 CAS 失败影响性能。因此它采用了类似LongAdder的设计baseCount基础计数器。CounterCell[] counterCells辅助计数数组每个线程可以独立更新自己的 CounterCell。cellsBusy自旋锁用于控制 counterCells 的初始化或扩容。当 CAS 更新baseCount失败时会尝试更新CounterCell如果仍失败则尝试扩容 counterCells 数组。最终size()返回baseCount sum(CounterCell)。2. 多线程协助扩容ConcurrentHashMap的扩容不是单线程完成而是允许多个线程共同参与。当某个线程发现需要扩容时它会设置sizeCtl为负数并创建ForwardingNode。其他线程在插入时如果遇到ForwardingNode会调用helpTransfer协助迁移数据。每个线程负责一个“步长”stride的桶通过 CAS 修改transferIndex来分配任务。迁移完成后将桶设为ForwardingNode后续操作自动转发到新数组。这种并发扩容机制使得扩容时间随参与线程数增加而缩短避免了单线程扩容时的长时间停顿。六、总结ConcurrentHashMap通过一系列精妙的设计在并发场景下实现了高性能的哈希表操作无锁读volatile保证可见性读操作不加锁性能接近HashMap。细粒度锁写操作只锁当前桶的头节点并发写入互不干扰。CAS 无锁更新空桶插入、计数更新等简单操作使用 CAS避免锁开销。多线程协助扩容将扩容任务分摊给多个写线程大幅减少扩容停顿时间。高效计数LongAdder思想分散计数压力高并发下依然准确高效。