发表于: 更新于: 浏览: 19

Java 7 的 ConcurrentHashMap

Java 7 的 ConcurrentHashMap 采用分段锁机制确保多线程安全。

ConcurrentHashMap 的内部类：Segment 用以表示分段，其继承 ReentrantLock以实现高并发下高效的加锁操作，内部的数据结构是哈希表+链表，由 volatile 关键字确保可见性。与一个普通 HashMap 类似，也维护负载因子，会自行扩容，可以看作是一个小型的、串行化的 HashMap。读操作不会加锁，写操作和扩容时加锁。

ConcurrentHashMap 的 HashEntry 也有些不同。V value 和 HashEntry<K,V> next 需要由 volatile 修饰，确保可见性。通过 Unsafe.objectFieldOffset 方法获取了 next 字段的偏移地址，以便直接使用 CAS 操作改变 next 的值。

ConcurrentHashMap 在初始化时需要指定并发级别（concurrencyLevel），初始化时会根据并发级别决定分段的数量。可以这么理解：并发级别为 n 代表一个 ConcurrentHashMap 最大能支持 n 个线程的并发读写。由于一个 Segment 只能同时支持一个线程的写操作，因此 Segment 的数量必须大于等于 n。并发级别默认为 16，Segment 的数量也默认为 16。特别地，Segment 数组的长度必须是 2 的整数次方，原因会在后文说明。因此，如果并发级别为 17，Segment 的数量将变为 32。

现在有一个 key，求出它的 hash 值（32 位 int 类型整数）后，应该如何路由到对应的 Segment？我们先来回想单个 HashMap 中 hash 值是如何映射到桶的。根据数据结构理论，如果桶数组的长度为 n，那么某个哈希值 hash 对应的桶下标应该是 hash % n。特别地，如果 n 是 2 的整数幂，那么这个取模运算可以被高效的位运算 hash & (n - 1) 代替。这也是为什么 HashMap 要求桶数组的长度必须是 2 的整数次方的原因。对于 Segment 路由，ConcurrentHashMap 采取了类似的思路，以 Segment 数量为 16 为例，先将 hash 值右移 32 - 4 位（剩下高四位），然后与 15，得到 Segment 的下标。

如果两个写操作发生竞争，ConcurrentHashMap 还采用了节点（HashEntry）预创建来优化并发性能。简单来说，如果一个线程在写操作时没有竞争到锁，那么它会转而自旋地检测 key 对应的节点是否存在，如果不存在，则预先创建它。这样，当它竞争到锁之后，可以缩短一些占用锁的时间。这种不浪费线程调度、充分让每个线程都有事可做的思路，是可以学习和迁移的。

Java 8 的 ConcurrentHashMap

Java 8 中的 ConcurrentHashMap 发生了重大变化，从代码规模上看，Java 7 的 ConcurrentHashMap 较为精短，总共代码 1.6k 行，而 Java 8 的 ConcurrentHashMap 来到了 6k 行，内部类的数量达到数十个...

Java 8 的 ConcurrentHashMap 抛弃了分段锁，而是采用粒度更低的桶级锁。数据结构变为 哈希表 + 链表/红黑树，HashEntry<K,V> 变为 Node<K,V> 、TreeBin<K,V> 和 TreeNode<K,V>，它们也都是 Entry<K,V> 的实现类。

在执行写操作时，ConcurrentHashMap 采用 CAS 操作和 synchronized 锁确保线程安全。你可以参阅下面这个流程图：

concurrentHashMap_putval.png

执行读操作同样是无锁的。ConcurrentHashMap 内部的实现确保读取时的一致性，例如读取操作不会访问到正在从链表转换为红黑树的中间状态的桶。然而这些内部实现导致 ConcurrentHashMap 的内存使用率进一步降低。

ConcurrentHashMap 的多线程扩容可以概括为如下过程：

  1. CAS 修改 sizeCtl 为 -1，指示当前处于扩容初始化阶段，这个阶段只需要一个线程进行：创建一个新数组 nextTable，大小是旧 table 的两倍。然后，赋值 sizeCtl 为旧容量 + 1，指示剩余需要迁移的桶数量。
  2. 其他线程观察到 sizeCtl > 0，即当前处于扩容阶段，可以主动加入迁移。
  3. transferIndex 用于不同线程之间分配迁移任务。每次线程加入迁移，将通过 CAS 竞争到 stride 个桶（默认 16），然后将 transferIndex 减少 stride。当 transferIndex 为负数，表示桶迁移任务全部分配完毕。
  4. 每当 1 个迁移完成，CAS 修改 sizeCtl--。当 sizeCtl = 0，表示桶迁移完成。
  5. 迁移完成后，用新表替换旧表，并且将 sizeCtl 修改为新的扩容阈值。

在扩容过程中，读取操作会同时访问新表和旧表，确保内容不会丢失。