探索 ConcurrentHashMap 高并发性的实现机制

核心提示：简介ConcurrentHashMap 是 util.concurrent 包的重要成员，本文将结合 Java 内存模型，探索 ConcurrentHashMap 高并发性的实现机制，分析 JDK 源代码，探索 ConcurrentHashMap 高并发的具体实现机制，找到 table 中对应的那个桶（table 数组

简介

ConcurrentHashMap 是 util.concurrent 包的重要成员。本文将结合 Java 内存模型，分析 JDK 源代码，探索 ConcurrentHashMap 高并发的具体实现机制。

由于 ConcurrentHashMap 的源代码实现依赖于 Java 内存模型，所以阅读本文需要读者了解 Java 内存模型。同时，ConcurrentHashMap 的源代码会涉及到散列算法和链表数据结构，所以，读者需要对散列算法和基于链表的数据结构有所了解。

Java 内存模型

由于 ConcurrentHashMap 是建立在 Java 内存模型基础上的，为了更好的理解 ConcurrentHashMap，让我们首先来了解一下 Java 的内存模型。

Java 语言的内存模型由一些规则组成，这些规则确定线程对内存的访问如何排序以及何时可以确保它们对线程是可见的。下面我们将分别介绍 Java 内存模型的重排序，内存可见性和 happens-before 关系。

重排序

内存模型描述了程序的可能行为。具体的编译器实现可以产生任意它喜欢的代码 -- 只要所有执行这些代码产生的结果，能够和内存模型预测的结果保持一致。这为编译器实现者提供了很大的自由，包括操作的重排序。

编译器生成指令的次序，可以不同于源代码所暗示的“显然”版本。重排序后的指令，对于优化执行以及成熟的全局寄存器分配算法的使用，都是大有脾益的，它使得程序在计算性能上有了很大的提升。

重排序类型包括：

• 编译器生成指令的次序，可以不同于源代码所暗示的“显然”版本。
• 处理器可以乱序或者并行的执行指令。
• 缓存会改变写入提交到主内存的变量的次序。

内存可见性

由于现代可共享内存的多处理器架构可能导致一个线程无法马上（甚至永远）看到另一个线程操作产生的结果。所以 Java 内存模型规定了 JVM 的一种最小保证：什么时候写入一个变量对其他线程可见。

在现代可共享内存的多处理器体系结构中每个处理器都有自己的缓存，并周期性的与主内存协调一致。假设线程 A 写入一个变量值 V，随后另一个线程 B 读取变量 V 的值，在下列情况下，线程 B 读取的值可能不是线程 A 写入的最新值：

• 执行线程 A 的处理器把变量 V 缓存到寄存器中。
• 执行线程 A 的处理器把变量 V 缓存到自己的缓存中，但还没有同步刷新到主内存中去。
• 执行线程 B 的处理器的缓存中有变量 V 的旧值。

Happens-before 关系

happens-before 关系保证：如果线程 A 与线程 B 满足 happens-before 关系，则线程 A 执行动作的结果对于线程 B 是可见的。如果两个操作未按 happens-before 排序，JVM 将可以对他们任意重排序。

下面介绍几个与理解 ConcurrentHashMap 有关的 happens-before 关系法则：

1. 程序次序法则：如果在程序中，所有动作 A 出现在动作 B 之前，则线程中的每动作 A 都 happens-before 于该线程中的每一个动作 B。
2. 监视器锁法则：对一个监视器的解锁 happens-before 于每个后续对同一监视器的加锁。
3. Volatile 变量法则：对 Volatile 域的写入操作 happens-before 于每个后续对同一 Volatile 的读操作。
4. 传递性：如果 A happens-before 于 B，且 B happens-before C，则 A happens-before C。

ConcurrentHashMap 的结构分析

为了更好的理解 ConcurrentHashMap 高并发的具体实现，让我们先探索它的结构模型。

ConcurrentHashMap 类中包含两个静态内部类 HashEntry 和 Segment。HashEntry 用来封装映射表的键 / 值对；Segment 用来充当锁的角色，每个 Segment 对象守护整个散列映射表的若干个桶。每个桶是由若干个 HashEntry 对象链接起来的链表。一个 ConcurrentHashMap 实例中包含由若干个 Segment 对象组成的数组。

HashEntry 类

HashEntry 用来封装散列映射表中的键值对。在 HashEntry 类中，key，hash 和 next 域都被声明为 final 型，value 域被声明为 volatile 型。

清单 1.HashEntry 类的定义  

				 
 static final class HashEntry { 
        final K key;                       // 声明 key 为 final 型
        final int hash;                   // 声明 hash 值为 final 型 
        volatile V value;                 // 声明 value 为 volatile 型
        final HashEntry next;      // 声明 next 为 final 型 

        HashEntry(K key, int hash, HashEntry next, V value) { 
            this.key = key; 
            this.hash = hash; 
            this.next = next; 
            this.value = value; 
        } 
 } 

在 ConcurrentHashMap 中，在散列时如果产生“碰撞”，将采用“分离链接法”来处理“碰撞”：把“碰撞”的 HashEntry 对象链接成一个链表。由于 HashEntry 的 next 域为 final 型，所以新节点只能在链表的表头处插入。下图是在一个空桶中依次插入 A，B，C 三个 HashEntry 对象后的结构图：

图 1. 插入三个节点后桶的结构示意图：  

注意：由于只能在表头插入，所以链表中节点的顺序和插入的顺序相反。

避免热点域

在 ConcurrentHashMap中，每一个 Segment 对象都有一个 count 对象来表示本 Segment 中包含的 HashEntry 对象的个数。这样当需要更新计数器时，不用锁定整个 ConcurrentHashMap。

Segment 类

Segment 类继承于 ReentrantLock 类，从而使得 Segment 对象能充当锁的角色。每个 Segment 对象用来守护其（成员对象 table 中）包含的若干个桶。

table 是一个由 HashEntry 对象组成的数组。table 数组的每一个数组成员就是散列映射表的一个桶。

count 变量是一个计数器，它表示每个 Segment 对象管理的 table 数组（若干个 HashEntry 组成的链表）包含的 HashEntry 对象的个数。每一个 Segment 对象都有一个 count 对象来表示本 Segment 中包含的 HashEntry 对象的总数。注意，之所以在每个 Segment 对象中包含一个计数器，而不是在 ConcurrentHashMap 中使用全局的计数器，是为了避免出现“热点域”而影响 ConcurrentHashMap 的并发性。

清单 2.Segment 类的定义  

				 
 static final class Segment extends ReentrantLock implements Serializable { 
        /** 
         * 在本 segment 范围内，包含的 HashEntry 元素的个数
         * 该变量被声明为 volatile 型
         */ 
        transient volatile int count; 

        /** 
         * table 被更新的次数
         */ 
        transient int modCount; 

        /** 
         * 当 table 中包含的 HashEntry 元素的个数超过本变量值时，触发 table 的再散列
         */ 
        transient int threshold; 

        /** 
         * table 是由 HashEntry 对象组成的数组
         * 如果散列时发生碰撞，碰撞的 HashEntry 对象就以链表的形式链接成一个链表
         * table 数组的数组成员代表散列映射表的一个桶
         * 每个 table 守护整个 ConcurrentHashMap 包含桶总数的一部分
         * 如果并发级别为 16，table 则守护 ConcurrentHashMap 包含的桶总数的 1/16 
         */ 
        transient volatile HashEntry[] table; 

        /** 
         * 装载因子
         */ 
        final float loadFactor; 

        Segment(int initialCapacity, float lf) { 
            loadFactor = lf; 
            setTable(HashEntry.newArray(initialCapacity)); 
        } 

        /** 
         * 设置 table 引用到这个新生成的 HashEntry 数组
         * 只能在持有锁或构造函数中调用本方法
         */ 
        void setTable(HashEntry[] newTable) { 
            // 计算临界阀值为新数组的长度与装载因子的乘积
            threshold = (int)(newTable.length * loadFactor); 
            table = newTable; 
        } 

        /** 
         * 根据 key 的散列值，找到 table 中对应的那个桶（table 数组的某个数组成员）
         */ 
        HashEntry getFirst(int hash) { 
            HashEntry[] tab = table; 
            // 把散列值与 table 数组长度减 1 的值相“与”，
 // 得到散列值对应的 table 数组的下标
            // 然后返回 table 数组中此下标对应的 HashEntry 元素
            return tab[hash & (tab.length - 1)]; 
        } 
 } 

下图是依次插入 ABC 三个 HashEntry 节点后，Segment 的结构示意图。