ConcurrentHashMap 简析

为什么需要 ConcurrentHashMap

Java 早期的同步类 HashTable 和 Collections 提供的同步包装器为我们提供了线程安全的容器，但是因为这两种方式都是在整个大操作 put、get、size 级别上加锁实现的。并发效率很低。作为改进，Java 提供了更为高效的并发容器——ConcurrentHashMap。

jdk 1.7 ConcurrentHashMap 分析

ConcurrentHashMap 的设计其实一直在演化，早期的 ConcurrentHashMap，其实现是基于：

• 分离锁，也就是将内部进行分段（Segment），里面则是 HashEntry 的数组，和 HashMap 类似，哈希相同的条目也是以链表的形式存放。
• HashEntry 内部使用 volatile 的 value 字段来保证可见性，也利用了不可变对象的机制以改进利用 Unsafe 提供的底层能力，比如 volatile access，去直接完成部分操作，以最优化性能，毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。

这个版本的核心是利用分段设计，在进行并发操作时，锁住相应的 Segment，来避免锁住整个表，大大提高了性能。

构造时，Segment 的数量由所谓的concurrentcyLevel 决定，默认是 16，可以通过构造函数显式指定，这个输入的值会被 Java 自动调整为最近的 2 的幂数值，比如输入 15，就会被自动调整为 16。之所以这样调整，是因为 2 的幂次方减一就是一个二进制低位全是 1 的“掩码”，在确定元素在哪个 Segment 时会利用到。

在进行并发写操作时：

• ConcurrentHashMap 会获取再入锁，以保证数据一致性，Segment 本身就是基于 ReentrantLock 的扩展实现的，所以，在并发修改期间，相应的 Segment 是被锁定的。
• 在最初阶段，进行重复性的扫描，以确定相应的 key 的值是否已经在数组里面，进而决定是更新还是放置操作。重复扫描、检测冲突是 ConcurrentHashMap 的常见技巧。

另一个需要关注的点是 size 方法，它的实现涉及分离锁的一个副作用。

如果不加锁直接计算所有 Segment 的总值，在并发 put 的情况下，就可能导致结果不准确，但是直接锁定所有 Segment 进行计算，代价就很昂贵。其实，分离锁也限制了 Map 的初始化等操作。

这个版本的 ConcurrentHashMap 是通过重试机制（RETRIES_BEFORE_LOCK，指定重试次数 2），来试图获得可靠值。如果没有监控到发生变化（通过对比 Segment.modCount)，就直接返回，否则获取锁进行操作。

jdk 1.8 ConcurrentHashMap 分析

• 总体结构上，它的内部存储结构变得和 HashMap 相似，同样是大的桶（bucket）数组，然后内部也是一个个所谓的链表结构（bin），同步的力度要更细致一些。在单个桶中数据过多时，会进行树化。
• 其内部保留了 Segment 定义，目的是为了保证序列化时的兼容性，不再有任何结构上的用处。
• 因为不再使用 Segment，初始化操作大大简化，修改为 lazy-load 形式，有效避免了初始开销，解决了老版本很多人抱怨的这一点。
• 数据存储利用 volatile 来保证可见性。
• 使用 CAS 等操作，在特定场景进行无锁并发操作。
• 使用 Unsafe、LongAdder 之类的底层手段，进行极端情况的优化。