ConcurrentHashMap源码阅读_JDK1.8(一)

一 API阅读

这个类的API算是比较长的了，逐字仔细看过。因为这个类有点大而且内容确实也足够丰富，整个看完有些花精力，这里先放出来一部分内容。剩下的有时间继续更吧。

哈希表(hashtable)支持高并发下的检索和更新操作。这个类遵循和hashtable一样的机制。尽管所有的操作都是线程安全的，检索操作还是没有涉及到锁并且也没有通过锁定整个table来保证数据访问的安全性。

检索操作通常不会阻塞，因此可能会与更新操作的重合(包括put与remove)。遍历的结果会反映出新近完成的更新操作的影响-即遍历操作虽然没有阻塞，但是还是会反映出其他线程最近修改的内容。 对于一些聚合性的操作(比如putAll和clear)，并发地检索只会反映出一部分的插入和更新内容。与之类似的Iterators遍历、Spliterators分隔和Enumerations枚举操作的返回元素的实效性取决于这些遍历器、枚举类型创建的时间。在创建后做出的修改操作可能不会被遍历操作同步。并且这些产生数据不一致的情况下，都不会抛出并发修改异常-ConcurrentModificationException。遍历器被设计成在某一时刻只能由一个线程来使用。留意那些聚合状态方法(比如size、isEmpty与containsValue)通常都没有对并发修改做出及时地反映。

当碰撞的概率变高时，table的size会动态扩展。其默认的加载因子仍然是0.75，一个考虑了空间与时间两方因素的折衷值。

注意这个类包含的元素是无序的，并且不同的遍历操作得到的顺序也不一致。

二设计思想

JDK 1.7

concurrenthashmap有相对更好的并发性能，其设计思想对此有很大影响。~~划重点~~分段锁思想了解一下。在一个实例中使用多个锁控制hashtable中不同的分段部分。在这里使用的是segment，每一个segment其实就是一个独立的小的hashtable，并且因为它继承了reentrantlock，所以每一个分段都已经拥有了锁。

结构性修改方法(比如put)会在确定分段后只锁住某一个segment，而不影响剩余段的操作。不过有一些方法存在跨段操作，比如size/containsValue等。这些方法就要按顺序锁住整个表来进行操作。

conHashMap_jdk1.7.png

update JDK1.8

在 JDK8 中，这部分的代码又有了新的变化，采用了新的设计思想，没有继续沿用 1.7 segment 分段锁。而是采用了 CAS + synchronized 关键字实现。整个数组的结构上在取消了 segment 之后，又和 hashMap 有了一些相似度。

conHashMap_jdk1.8.png

三源码

3.1 类中的静态字段

private static final int MAXIMUM_CAPACITY = 1 << 30;

table 的最大容量，一个位运算得到的值即2的三十次方，换算过来大约是10亿。其实在源码中可以看到大量的位运算操作，我们在实际编码中有些内容也可以适当采用位运算来处理。最大的好处在于快。

private static final int DEFAULT_CAPACITY = 16;

table 的默认容量值16，注释要求 table 的容量值必须是 2 的幂。其可取的最大值为 MAXIMUM_CAPACITY。

static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

数组的最大长度值，提到说这个静态常量用于 toArray 和其他的相关方法。

private static final int DEFAULT_CONCURRENCY_LEVEL = 16;

默认的 concurrentHashMap 并发度-16。即默认构造函数创建的实例，其并发度都是16。并发度直接表明一个 map 实例允许被多个线程同时操作的最大值。我们可以使用含参的构造函数来指定初始化并发度，但是输入的值不一定的最终得到实例的实际并发度，这里会取大于等于这个入参的 2 的最小的幂值。比如

new ConcurrentHashMap<>(17);

实际会得到一个并发度为 32 的实例。

private static final float LOAD_FACTOR = 0.75f;

装载因子，这个初始值和 hashMap 的装载因子初始值一致。

static final int TREEIFY_THRESHOLD = 8;

进行树型结构转换的临界值，这个值依然和 hashMap 的取值一致。在散列桶中，当某个节点和其后继节点的总长度大于 8 就会引发树型结构转换。

static final int UNTREEIFY_THRESHOLD = 6;

在一个桶变成树结构后，由树结构转换为链表的临界值。注意这里就和 hashmap 由一些差别了，hashmap 的“链表转换树”和“树转换链表的”临界值是固定的 8。hashmap 里“链表转换树” 的临界值为 6，“树转换为链表”的临界值为 8。

static final int MIN_TREEIFY_CAPACITY = 64;

桶中的某个链表转换为树结构时，concurrentHashMap 所需要的最低容量值。前面有一个默认容量值为 16，也就是说如果 map 中已经存在树结构的桶节点，那么当前 map 的容量是肯定大于16(如果是默认的构造函数创建的实例，那么这个实例也一定是有过扩容操作的)。MIN_TREEIFY_CAPACITY 的值至少是 TREEIFY_THRESHOLD 的 4 倍。

private static final int MIN_TRANSFER_STRIDE = 16;

最小转移值 //TODO

private transient volatile int sizeCtl;

状态标识控制符。这个字段在 conHashMap 中的应用比较广泛。根据注释指明：当它为负数的时候，table 处于正在初始化或者扩容的阶段；-1表示初始化，其余的负数表示扩容，负数的绝对值表示此刻有几个线程正在执行扩容。

3.2 类中的内部类

static class Node<K,V> implements Map.Entry<K,V> {

Node 节点，其中包含 4 个类成员

final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;

node 里的 key 及其对应的 hash 值。 注意其 val 和 next 节点的引用指向使用了 volatile 关键字修饰。 所以这两个字段在多线程环境下的并发修改都会对其他线程可见。

这里的 node 节点的 setValue() 方法不被支持，直接调用会抛出 UnsupportedOperationException 异常，也就是说一旦使用构造器初始化一个 node 节点，这个 node 节点的 val 就已经确定并且不能再被修改。

public final V setValue(V value) {
        throw new UnsupportedOperationException();
    }

还对外提供一个检索方法

find(int h, Object k)

这个方法用来检索单向链表中是否存在一个 hashCode == h && key.equals(k) 的 node 子节点。

3.3 put 操作

table 在调用构造函数后没有实际上地完成初始化动作，只有在第一次向其中 put 元素的时候才会触发这个动作。因此我们先看一看在实例化了一个 map 后的第一次 put 操作逻辑。

    public V put(K key, V value) {
        return putVal(key, value, false);
    }
    
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        if (key == null || value == null) throw new NullPointerException();
        int hash = spread(key.hashCode()); 计算得到 key 对应的 hashCode
        int binCount = 0; 
        for (Node<K,V>[] tab = table;;) {
            Node<K,V> f; int n, i, fh;
            if (tab == null || (n = tab.length) == 0)
                tab = initTable(); // table 初始化方法
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 检查 tab 中对应位置的元素是否为空
                if (casTabAt(tab, i, null,
                             new Node<K,V>(hash, key, value, null))) // 不为空则执行 cas 替换，注意这里的操作没有加锁
                    break;                   // no lock when adding to empty bin
            }
            else if ((fh = f.hash) == MOVED) // 判断这个节点的 hash 值是否是 -1 即当前节点是否正在被扩容，如果是的话，当前线程会执行协助扩容的方法。
                tab = helpTransfer(tab, f);
            else { // 前述两种情况都不满足的情况下就执行 synchronized 同步代码块。
                V oldVal = null;
                synchronized (f) {
                    if (tabAt(tab, i) == f) { // 再次检查对应位置上的节点是不是同一个节点，此后不需要再检查是因为代码已经进入同步块，在当前线程没有释放锁的前提下这个节点的位置就不可能被其他线程改变了。
                        if (fh >= 0) {
                            binCount = 1;
                            for (Node<K,V> e = f;; ++binCount) {
                                K ek;
                                if (e.hash == hash &&
                                    ((ek = e.key) == key ||
                                     (ek != null && key.equals(ek)))) { // 如果定位到的节点值不为 null 则替换节点值，并缓存节点的旧的 value 值，注意这里的判断是同时判断 key 与 value 都要匹配。
                                    oldVal = e.val;
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K,V> pred = e;
                                if ((e = e.next) == null) { // 新的 node 节点是执行尾插法
                                    pred.next = new Node<K,V>(hash, key,
                                                              value, null);
                                    break;
                                }
                            }
                        }
                        else if (f instanceof TreeBin) { // 判断是不是树节点，如果是树节点的话就执行另一套插入逻辑
                            Node<K,V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                           value)) != null) {
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                if (binCount != 0) {
                    if (binCount >= TREEIFY_THRESHOLD) // 扩容临界值检查，如果超过的话会检查确定是否做树结构转换
                        treeifyBin(tab, i);
                    if (oldVal != null)
                        return oldVal; // 如果之前定位到的 map 上的节点不为空，那么返回这个节点上的之前的值
                    break;
                }
            }
        }
        addCount(1L, binCount); // binCount 值累加
        return null; // 定位到的节点之前为 null，那么就返回null表示 putVal 操作是在一个 null 节点上做的插入操作
    }

其中的初始化方法

    /**
     * Initializes table, using the size recorded in sizeCtl.
     */
    private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) { // 判断 table 的长度、table 是否为空
            if ((sc = sizeCtl) < 0) // 如果标识符 sizeCtl 小于零，则表示此时 table 正在被其他线程扩容或者执行初始化操作，让出当前的 CPU 时间片。
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 标识符大于等于 0。CAS 比较替换
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY; // 确定创建的 table 数组长度
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt; // 赋值操作
                        sc = n - (n >>> 2); // 给 sc 赋值，这个 sc 的值最后会赋给 sizeCtl。
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

代码里的 CAS 机制方法是一个 native 方法，此处不编译出对应的源码比对了。CAS 操作是为了修改类中的 sizeCtl 变量。此时 sizeCtl 的值修改为了 -1。修改成功后，try/catch 语句块再一次检查table是否依然没有被初始化。如果没有则创建一个长度为 16 的 node 数组并赋值给 table。当 sizeCtl 修改为负数之后，其他的线程在执行扩容操作时就无法成功，它们会即刻让出当前的 CPU 时间片。

这个 if 语句块内的操作，有点类似于单例设计模式-懒加载-doubleCheck 的流程。当然整个过程没有显示的加锁。而是通过 CAS 技巧完成。

除了初始化，剩下的大头内容就是 put 操作内的了。这里可以结合我在代码里的注解简述put操作的流程

检查按位与操作定位出来的元素位置是否为 null，如果是的话直接使用 CAS 比较替换插入元素。
检查当前节点的 hash 码，如果能确定当前节点类型是 ForwardingNode，表明当前有其他线程正在实行扩容操作，当前线程也加入扩容操作流程，将当前节点加入到 nextTable 中。
如果定位出来的位置已经存在元素并且当前节点也不属于 ForwardingNode，那么使用 synchronized 关键字锁住这个节点，注意这里锁住的不是整个数组，而是数组内的某一个 node 节点。这样我们也其实相当于实现了“分段锁”的概念。但是与 JDK1.7 不同的是，这里使用了更加轻量级的 synchronized 关键字，并且锁住的数据区域更细粒度，条件检测更加精确。
判断单向链表内的 size，如果 size 大于等于 8 就要做数据结构转换，即由一个单向的链表转换为红黑树。注意这里与 HashMap 的区别，concurrentHashMap 有一个“链表转换为红黑树”的阀值，还有一个“红黑树转换为链表”的阀值并且这 两个阀值不一样。

ConcurrentHashMap源码阅读_JDK1.8(一)

一 API阅读

二 设计思想

三 源码

3.1 类中的静态字段

3.2 类中的内部类

3.3 put 操作

推荐阅读更多精彩内容

二设计思想

三源码