1.JDK1.8中的CurrentHashMap的源码分析

文章目录

• 1.无参构造，根据使用流程分析

1.无参构造，根据使用流程分析

1. 无参构造

jdk1.8中的无参构造非常简单，看源码，无参构造什么都没有做。

public ConcurrentHashMap() {
}

接下来看以看put方法是怎么实现的，在put中应该会进行初始化

2. put 方法

put方法调用了内部的一个 putVal的方法，让putVal进行具体的添加操作

public V put(K key, V value) {
    return putVal(key, value, false);
}

3. putVal 方法

由于 putVal 方法的代码比较多，这里将源码复制出来，在代码上边写注释，最后做总结的方式进行分析。

这里的代码中，用换行的方式将每一段小逻辑进行分割

final V putVal(K key, V value, boolean onlyIfAbsent) {
 	// key 和 value 都不能为 null
    if (key == null || value == null) throw new NullPointerException();
    
    // 通过key的hash值进行计算，算出一个hash值
    int hash = spread(key.hashCode());
    int binCount = 0;
    
    // 这里进行了一次赋值，tab=table，然后执行死循环，循环中是一连串if-else，要理清楚
    // table 是一个 Node[]，存放的就是 key 和 value 的节点
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; 
        int n, i, fh;
        
        // 如果数组为 null，就对数组进行初始化操作，初始化后长度为16，阈值是12
        // 如果数组不为 null，会给 n赋值， n=tab.lengtn，这里体现了 || 的作用
        if (tab == null || (n = tab.length) == 0)
            tab = initTable();
        
        // 到这里的时候，tab数组已经保证不是 null 了
        // 先进行了 (n - 1) & hash 的操作，算出要添加的元素应该在数组中的那个位置
        // 这里还将 数组中第i个元素的值 赋给了 变量f
        // 如果数组中的第 i 个位置没有元素，则尝试进行对这个位置的元素赋值 new Node
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
            // 如果赋值成功，则添加成功，跳出循环，失败则继续下一次循环。也就是所谓的自旋
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }

        // 能执行这个判断，说明该位置有值，
        // 上边的判断中，把这个位置的值赋给了 f ，所以f.hash也就是该位置元素的hash值
        // 这个判断也将 f.hash 赋给了 fh变量
        // MOVED 表示当前ConcurrentHashMap正在进行扩容
        // 如果当前ConcurrentHashMap正在扩容，当前线程会帮助它扩容
        else if ((fh = f.hash) == MOVED)
            tab = helpTransfer(tab, f);

        // 执行到这里的时候，说明当前ConcurrentHashMap没有在扩容，并且要添加的位置已经有元素了
        // 但是并不知道是链表结构还是树结构
        else {
            V oldVal = null;
            // 对之后的操作进行加锁，头节点充当锁
            // 不同线程操作不同的数组节点的时候，是不会阻塞的。因为用的不是同一把锁
            synchronized (f) {
                // 确认在加锁过程中没有其他线程更改了头节点，也就是使用的锁
                if (tabAt(tab, i) == f) {
                    // 如果节点的hash值 >= 0 表示是链表上的节点
                    if (fh >= 0) {
                        // 记录节点个数
                        binCount = 1;
                        // 对链表进行遍历
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果当前元素和要添加的元素的key相同，则替换这个key的value
                            if (e.hash == hash &&
                                ((ek = e.key) == key ||
                                 (ek != null && key.equals(ek)))) {
                                oldVal = e.val;
                                // 安全替换该key的value
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            Node<K,V> pred = e;
                            // 如果是尾节点，则表示该链表中没有这个Key的元素，就在后边添加这个元素
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    // 如果f的类型是TreeBin，TreeBin是ConcurrentHashMap的一个内部类，包装了ThreeNode
                    else if (f instanceof TreeBin) {
                        Node<K,V> p;
                        binCount = 2;
                        // 将传来的 key，value值put到这课树中，若存在相同key则替换value
                        // TreeBin在put的时候，该树中已存在相同的key，则会返回key相同的节点，若不存在相同的key则返回null
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // 这部分不论树还是链表都需要执行的
            // binCount = 0 表示头节点被人动了手脚，继续下次循环
            // binCount 是记录这个节点下有多少元素的变量，主要针对链表状态，检查是否需要转变为树
            if (binCount != 0) {
                // 如果节点下的元素个数 >= 8，则将链表树化
                if (binCount >= TREEIFY_THRESHOLD)
                    treeifyBin(tab, i);
                // 如果这次是替换（key已存在），返回旧的value值
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 增加元素的个数，也就是size，并且在这个方法中判断是否需要扩容
    addCount(1L, binCount);
    return null;
}

4. addCount 方法

private final void addCount(long x, int check) {
    CounterCell[] as; 
    long b, s;
    // counterCells 计数格子
    // 先给as赋值 as = counterCells，
    // 如果是null还没有被初始化 则进行cas算法，试着将 baseCount 改为 baseCount + x，执行 cas 算法成功的线程，不执行里边的逻辑，执行失败的线程进入if执行
    // 如果 counterCells 不是 null，直接执行里边的逻辑
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; 
        long v; int m;
        boolean uncontended = true;
        // 如果 counterCells 是null，或者长度<=0 
        // 或者线程要在 counterCells 中使用的位置没有元素
        // 或者 使用cas算法对 CELLVALUE + 1 的操作失败了
        // 就执行逻辑中的代码
        if (as == null || (m = as.length - 1) < 0 ||
            // ThreadLocalRandom.getProbe() 线程生成一个随机数
            (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
            !(uncontended =
              U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
            // 如果没有对应的就新建，有就对值+1
            fullAddCount(x, uncontended);
            return;
        }
        // 如果添加的位置不是链表或者红黑树，或者执行的是删除操作，直接结束方法
        if (check <= 1)
            return;
        // 添加完成之后统计ConCurrentHashMap的元素个数
        s = sumCount();
    }
    
    // 如果执行的是添加操作
    if (check >= 0) {
        Node<K,V>[] tab, nt; 
        int n, sc;
        // 如果当前个数 >= 阈值 并且 数组不为 null
        // 并且 数组长度 < 最大容量 则进行扩容
        while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
               (n = tab.length) < MAXIMUM_CAPACITY) {
            // 调整大小的标记位
            int rs = resizeStamp(n);
            if (sc < 0) {
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                    transferIndex <= 0)
                    break;
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                    transfer(tab, nt);
            }
            
            // rs << RESIZE_STAMP_SHIFT 对标记位左移RESIZE_STAMP_SHIFT位后，一定是一个负数
            else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                         (rs << RESIZE_STAMP_SHIFT) + 2))
                // 转移
                transfer(tab, null);
            s = sumCount();
        }
    }
}

5. fullAddCount 方法

private final void fullAddCount(long x, boolean wasUncontended) {
    int h;
    // 获取线程probe作为的hash值，同一个线程这个值是不会变的
    if ((h = ThreadLocalRandom.getProbe()) == 0) {
        // 强制初始化
        ThreadLocalRandom.localInit();      // force initialization
        h = ThreadLocalRandom.getProbe();
        wasUncontended = true;
    }
    
    // 控制扩容
    boolean collide = false;                // True if last slot nonempty
    // 死循环（自旋）
    for (;;) {
        CounterCell[] as; 
        CounterCell a; 
        int n; 
        long v;
        
        // 如果counterCells数组不是null
        if ((as = counterCells) != null && (n = as.length) > 0) {
            // 根据h与数组长度算出在counterCells数组中的下标，看这个位置是否为null
            
            if ((a = as[(n - 1) & h]) == null) {
                // 如果位置是null，则判断cells是否在忙
                if (cellsBusy == 0) {            // Try to attach new Cell
                    // 如果不忙，则新建Cell，初始值是 1
                    CounterCell r = new CounterCell(x); // Optimistic create
                    // 再次判断cell是否在忙，
                    // 如果不忙再使用cas算法试图将它的状态改为 1，表示在忙，然后执行改分支
                    // 修改失败 或 在忙 则自旋，继续下一次循环
                    if (cellsBusy == 0 &&
                        U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {                    
                        boolean created = false;
                        try {               // Recheck under lock
                            CounterCell[] rs; 
                            int m, j;
                            // 再次判断这个数组是否为null
                            // 再次判断数组要使用的位置是否为null
                            if ((rs = counterCells) != null &&
                                (m = rs.length) > 0 &&
                                rs[j = (m - 1) & h] == null) {
                                // 满足条件则给位置赋值，并标记新建成功
                                rs[j] = r;
                                created = true;
                            }
                        } finally {
                            // 最后将数组声明为不忙（释放该数组）
                            cellsBusy = 0;
                        }
                        // 新建成功则跳出循环（自旋）
                        if (created)
                            break;
                        // 失败则继续循环
                        continue;           // Slot is now non-empty
                    }
                }
                collide = false;
            }
            
            // 若对应位置有元素，则将传入的false改为true，然后执行后边的语句，重新生成hash值，再次进行循环
            else if (!wasUncontended)       // CAS already known to fail
                wasUncontended = true;      // Continue after rehash
            // 执行到这里表示：需要使用的位置已经有元素了，并且更改过了wasUncontended的状态，重新计算了hash，但再次需要使用的位置上依旧有元素
            // 这时尝试修改这个位置元素的值，成功则退出
            else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
                break;
            
            // 如果数组发生了变化，或者 数组长度>=cpu核心数，禁止扩容
            else if (counterCells != as || n >= NCPU)
                collide = false;            // At max size or stale
            // 如果禁止扩容，则打开扩容，然后再次循环。
            else if (!collide)
                collide = true;
            // 如果数组没有在忙，则尝试改为再忙，修改成功则执行扩容逻辑
            else if (cellsBusy == 0 &&
                     U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
                try {
                    // 如果数组对象没有改变
                    if (counterCells == as) {// Expand table unless stale
                        // 容量扩容一倍
                        CounterCell[] rs = new CounterCell[n << 1];
                        for (int i = 0; i < n; ++i)
                            rs[i] = as[i];
                        counterCells = rs;
                    }
                } finally {
                    // 改为不忙的状态
                    cellsBusy = 0;
                }
                // 限制扩容
                collide = false;
                continue;                   // Retry with expanded table
            }
            // 再次生成hash值
            h = ThreadLocalRandom.advanceProbe(h);
        }
        
        // cellsBusy 表示当前数组位置是否被其他线程在使用 0表示没有
        // 如果当前数组没有在忙，并且数组没有被其他线程改变 null
        // 如果使用cas算法将cellsBusy改成了1，则执行if中的逻辑
        else if (cellsBusy == 0 && counterCells == as &&
                 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
            boolean init = false;
            try {                           // Initialize table
                // 判断 counterCells 是否还是null
                if (counterCells == as) {
                    // 创建长度为2的一个CounterCell数组
                    CounterCell[] rs = new CounterCell[2];
                    // 在数组适当位置创建CounterCell，值为 1
                    // h & 1 的值只会是 0 或 1
                    rs[h & 1] = new CounterCell(x);
                    // 给counterCells 赋值
                    counterCells = rs;
                    // 标记初始化成功
                    init = true;
                }
            } finally {
                // 最后将数组恢复为闲置状态
                cellsBusy = 0;
            }
            // 初始化成功则退出循环（自旋）
            if (init)
                break;
        }
        
        // 如果不满足上述两个分支，则再次改变baseCount属性，成功改变则退出循环（自旋）
        // 增加一个选择
        else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
            break;                          // Fall back on using base
    }
}