注:本章的代码均基于 JDK 1.8.0_111
Java 7 为实现并行访问,引入了 Segment 这一结构,实现了分段锁,理论上最大并发度与 Segment 个数相等。Java 8 为进一步提高并发性,摒弃了分段锁的方案,而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能,Java 8 在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为 O(N))转换为红黑树(寻址时间复杂度为 O(long(N)))。其数据结构如下图所示
Java 8 的 ConcurrentHashMap 同样是通过 Key 的哈希值与数组长度取模确定该 Key 在数组中的索引。同样为了避免不太好的 Key 的 hashCode 设计,它通过如下方法计算得到 Key 的最终哈希值。不同的是,Java 8 的 ConcurrentHashMap 作者认为引入红黑树后,即使哈希冲突比较严重,寻址效率也足够高,所以作者并未在哈希值的计算上做过多设计,只是将 Key 的 hashCode 值与其高 16 位作异或并保证最高位为 0(从而保证最终结果为正整数)。
对于 put 操作,如果 Key 对应的数组元素为 null,则通过 CAS 操作 将其设置为当前值。如果 Key 对应的数组元素(也即链表表头或者树的根元素)不为 null,则对该元素使用 synchronized 关键字申请锁,然后进行操作。如果该 put 操作使得当前链表长度超过一定阈值,则将该链表转换为树,从而提高寻址效率。
对于读操作,由于数组被 volatile 关键字修饰,因此不用担心数组的可见性问题。同时每个元素是一个 Node 实例(Java 7 中每个元素是一个 HashEntry),它的 Key 值和 hash 值都由 final 修饰,不可变更,无须关心它们被修改后的可见性问题。而其 Value 及对下一个元素的引用由 volatile 修饰,可见性也有保障。
对于 Key 对应的数组元素的可见性,由 Unsafe 的 getObjectVolatile 方法保证。
put 方法和 remove 方法都会通过 addCount 方法维护 Map 的 size。size 方法通过 sumCount 获取由 addCount 方法维护的 Map 的 size。
来源: http://www.jasongj.com/java/concurrenthashmap/