【JUC并发编程】11 ConcurrentHashMap如何计算Size

绝地灬酷狼 2023-10-02 15:11 4阅读 0赞

## 一、前言 ##

我们都知道，ConcurrentHashmap这个并发集合框架是线程安全的。然而，他的size()操作中并没有加任何锁，它是如何在多线程环境下 线程安全的计算出Map的size的？下面我们就来看一下size()方法。

## 二、ConCurrentHashMap\#size()方法 ##

### 1、原理 ###

**size()使用sumCount()方法计算map的size。**

*  对于size的计算，在扩容和addCount()方法已经有所处理了；
 *  JDK1.8 ConCurrentHashMap的大小 size 通过 `baseCount` 和 `counterCells` 两个变量维护：
    
    1.  在没有并发的情况下，使用一个`volatile修饰`的 `baseCount` 变量即可；
    2.  当有并发时，CAS `修改 baseCount 失败后`，会`使用 CounterCell 类`，即 创建一个CounterCell对象，设置其`volatile修饰`的 `value` 属性为 1，并将其放在ConterCells数组的随机位置；
 *  最终在sumCount()方法中通过累加 baseCount和CounterCells数组里每个CounterCell的值 得出Map的总大小Size。
 *  然而 返回的值是一个估计值；如果有并发插入或者删除操作，和实际的数量可能有所不同。
 *  另外`size()方法的最大值`是 `Integer` 类型的`最大值`，而 Map 的 size 有可能超过 Integer.MAX\_VALUE，所以JAVA8 `建议使用 mappingCount()`。

### 2、源码分析 ###

我们直接看一下JAVA8 ConCurrentHashMap的size()方法代码：

public int size() {
        
        // 真正计算Size的地方
        long n = sumCount();
        return ((n < 0L) ? 0 : // if n < 0 return 0
                (n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE : // else if n > int.maxValue return int.maxValue
                        (int) n); // else return (int)n。
    }

size()的最大值是 Integer 类型的最大值，但是 Map 的 size 可能会超过 Integer.MAX\_VALUE， 然而还有一个用来计算Map 的 size 的方法 `mappingCount()`返回的最大值是Long的最大值，所以JAVA8建议使用 mappingCount() 而不是size()。

**mappingCount() 的代码如下：**

public long mappingCount() {
        
        long n = sumCount();
        return (n < 0L) ? 0L : n; // ignore transient negative values
    }

以上可以看出，无论是 size() 还是 mappingCount(), 计算Map大小的核心方法都是 `sumCount()`。

#### sumCount()方法： ####

> 若counterCells不为null，`sumCount()` 中迭代 counterCells ，然后和baseCount累加来统计Map的Size。

final long sumCount() {
        
        CounterCell[] as = counterCells;
        // CAS修改baseCount失败后，使用CounterCell用来统计那个线程要修改的
        CounterCell a;
        // 当没有并发竞争的时候，只使用baseCount统计map的size。
        long sum = baseCount;
        // 遍历counterCells，将CounterCell数组中元素的 value 累加 到 sum变量上。
        if (as != null) {
        
            for (int i = 0; i < as.length; ++i) {
        
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        // 这个数字可能是不准确的,所以ConCurrentHashMap的size是一个参考值，并不是实时确切值。
        return sum;
    }

ConcurrentHashMap 提供了 baseCount、counterCells 两个变量和一个 CounterCell 内部类用来统计Map的大小size。

// size的基本计数值，主要在没有线程并发争用时使用
    private transient volatile long baseCount;
    
    /**
     * Table of counter cells. When non-null, size is a power of 2.
     */
    private transient volatile CounterCell[] counterCells;
    /**
     * @sun.misc.Contended 这个注解的作用是防止伪共享，
     * 使用时，需要加上 -XX:-RestrictContended 参数
     */
    @sun.misc.Contended
    static final class CounterCell {
        
        volatile long value;
    
        CounterCell(long x) {
        
            value = x;
        }
    }

**伪共享概述：**

> 1.  `缓存系统`中是以`缓存行`（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节；最常见的`缓存行大小是64个字节`。
> 2.  当`多线程修改`互相独立的变量时，如果这些变量`共享同一个缓存行`，就会无意中`影响彼此的性能`，这就是`伪共享`。

既然统计Map的size需要迭代counterCells，那么`counterCells是哪里维护的？`  
我们看一下Map的`put()`操作，它指定会影响counterCells。put()方法中`最终会调用addCount()`修改Map的size。  
![在这里插入图片描述][4d5e65930fd04105a8c491ee03de7c60.png]

#### addCount()方法： ####

**addCount()方法分为两个阶段，分别为：**

1.  计算当前存入的KV键值对总数size；
2.  存储的总kv数量达到了阈值，执行扩容

**针对第一阶段：**

*  首先第一次执行addCount()方法时，counterCells数组为null，则`(as = counterCells) != null`为false，所以线程直接使用CAS将`baseCount`执行 +v操作；
 *  如果CAS失败 或 第N次执行`addCount()`方法时发现counterCells不为空，会做进一步判断，包括：
    
    1> counterCells等于null（第一次CAS修改baseCount值失败时）
    
    2> 或 counterCells初始化了但是其中没有数据 或 counterCells中随机一个下标位置a处没有存储数据
    
    3> 或 对counterCells下标位置a处执行CAS做 + v操作失败了；
 *  进入到`fullAddCount()`方法中进一步处理多线程竞争下的键值对size维护操作；
 *  并使用一个boolean类型的变量uncontended标记是否为对counterCells下标位置a处执行CAS失败才进入的`fullAddCount()`方法，false表示是。

private final void addCount(long x, int check) {
        
        CounterCell[] as;
        long b, s;
        /**
         * part1: 计算当前存入的KV键值对总数
         */
        if ((as = counterCells) != null || /** 第一次执行这段的时候，counterCells等于null */
                !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
         /** 如果此处产生多线程竞争，则只有一条线程可以执行成功，且不用进入if语句中 */
            CounterCell a;
            long v;
            int m;
            boolean uncontended = true;
            if (as == null || /** 如果counterCells等于null */
                    (m = as.length - 1) < 0 || /** 如果counterCells初始化了但是里面没有元素 */
                    (a = as[ThreadLocalRandom.getProbe() & m]) == null || /** 如果随机一个下标位置但是没有存储数据 */
                    !(uncontended =
                            U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
         /** 如果多线程竞争失败，则会执行fullAddCount方法 */
                // 使用CounterCell来计数
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            // 统计所有count值
            s = sumCount();
        }
        if (check >= 0) {
        
            Node<K, V>[] tab, nt;
            int n, sc;
            /**
             * part2: 存储的总kv数量达到了阈值，执行扩容
             *
             * s>=sizeCtl，表示达到了扩容的阈值
             */
            while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
                    (n = tab.length) < MAXIMUM_CAPACITY) {
        
                int rs = resizeStamp(n);
                // sc为负值，表明正在执行扩容操作中
                if (sc < 0) {
        
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || /** sc右移16位，则读取的就是原高16位的内容，即：table容量相关信息;不等于rs说明table容量发生了不一致的情况 */
                            sc == rs + 1 ||
                            sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                            transferIndex <= 0)
                        break;
                    // 加入1个共同扩容的线程，即：sc+1
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                } else if (U.compareAndSwapInt(this, SIZECTL, sc,
                        (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                // 统计所有count值
                s = sumCount();
            }
        }
    }

扩容部分后面博文介绍。

我们接着看fullAddCount()是怎么处理多线程竞争条件下的key-value键值对的size。

#### fullAddCount()方法： ####

**fullAddCount()又可以分为两个阶段：**

*  第一阶段，计算当前线程的探针哈希值；
 *  第二阶段，在无限循环中，利用CounterCell进行计数。

**第一阶段比较简单：**

主要逻辑为：如果获取到的随机数为0，则初始化当前线程的探针哈希值；并再次获取到当前线程的探针哈希值。探针哈希值的操作主要涉及三个方法：

*  **ThreadLocalRandom.getProbe()**：用来获得随机数；
 *  **ThreadLocalRandom.localInit()**：初始化当前线程的探针哈希值；
 *  **ThreadLocalRandom.advanceProbe(h)**：更改当前线程的探针哈希值。

**面试官：聊一下探针哈希值的作用？**  
**秃秃：**探针哈希值的作用是哈希线程，将线程和数组中的不同元素对应起来，尽量避免线程争用同一数组元素。

**面试官：探针哈希值和map里使用的哈希值的区别什么？**  
**秃秃：**当线程发生数组元素争用后，可以改变线程的探针哈希值，让线程去使用另一个数组元素，而map中key对象的哈希值，由于有定位value的需求，所以它是一定不能变的。

**第二阶段包含三种情况：**

1.  counterCells不为空且其中有元素；
2.  counterCells为空，且没有其他线程正在操作counterCells；
3.  尝试直接通过CAS修改baseCount的值；

我们先通过两张图分别介绍一下：有线程竞争CAS修改同一counterCells下标位置的值、和无线程竞争时的场景：

**1）无线程竞争时：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]

**2）有线程竞争CAS修改同一counterCells下标位置的值：**  
![在这里插入图片描述][935718cd34054fadb928ab56b8102e57.png]

**part1>** 第一种情况：counterCells不为空且其中有元素；

**这其中又包含四种case：**

1、随机数h待插入的counterCells数组下标位置没有数据；并且没有线程正在操作counterCells数组，则通过CAS将cellsBusy设置为1，然后新建一个CounterCell插入到 随机数`h & counterCells.length`下标位置，在将cellsBusy设置为0；

2、随机数h待插入的counterCells数组下标位置有数据，则通过CAS将原数据值 + v；CAS成功退出循环；

3、否则，判断counterCells数组是否发生了变化（即是否已经扩容），发生变化 则将collide设置为true，表示发生了碰撞。

4、如果多线程CAScounterCells 指定下标位置的value值时发生碰撞，CAS的失败的线程会对counterCells数组进行两倍扩容，以减少碰撞次数。

**part2>** 第二种情况：counterCells为空，且没有其他线程正在操作counterCells；

*  直接创建一个长度为2的CounterCell数组counterCells，并将x赋值进数组的 `h & 1`下标位置，跳出循环。

**part3>** 第三种情况：尝试直接通过CAS修改baseCount的值；

*  如果CAS修改baseCount成功，则跳出循环，否则继续下一轮循环。

**面试官：标注CounterCell的注解`@sun.misc.Contended`的作用是什么？**

**秃秃：**`@sun.misc.Contended`是Java8新增的一个注解，对某个字段加上该注解 则表示该字段会单独占用一个缓存行（Cache Line）；

*  缓存行是指CPU缓存（L1、L2、L3）的存储单元，常见的缓存行大小为64字节；
 *  JVM添加-XX:-RestrictContended参数后@sun.misc.Contended注解才有效。

**面试官：单独使用一个缓存行有什么作用？**

**秃秃：**避免伪共享；

*  为了提高读取速度，每个CPU都有自己的缓存，CPU读取数据后会存到自己的缓存里；并且为了节省空间，一个缓存行可能存储着多个变量，即**伪共享**。
 *  但是伪共享对于共享变量，会造成性能问题，比如：
    
    1.  当一个CPU要修改共享变量A时会先锁定自己缓存里 A所在的缓存行，并且把其他CPU缓存上相关的缓存行设置为无效。
    2.  但如果被锁定或失效的缓存行里，还存储了其他不相干的变量B，其他线程此时就访问不了B。
    3.  或者由于缓存行失效需要重新从内存中读取加载到缓存里，也就造成了开销。
    4.  所以让共享变量A单独使用一个缓存行就不会影响到其他线程对其他共享变量的访问。

**面试官：Java8之前避免伪共享的方案是什么？**

**秃秃：**在Java7之前，是通过代码里手动添加属性的方式解决的，比如类A中有一个long类型的value；因为一个long占8个字节，所以再添加7个long属性就会变成64个字节，刚好是一个缓存行大小。

class A {
        
    	long value;
    	long p0, p1, p2, p3, p4, p5, p6;
    }

*  但是，Java7开始，JVM做优化时可能会把不用的变量给去掉，所以不推荐使用这种方案。

**面试官：@sun.misc.Contended有什么适用场景？**

**秃秃：**主要适用于会被频繁写的共享数据上。如果不是频繁写的数据，那么CPU缓存行被锁的几率就不大，所以没必要使用；否则不仅占空间还会浪费CPU访问/操作数据的时间。

## 三、总结 ##

Java8的ConCurrentHashMap的size在addCount()中已经有了初步的维护，非并发场景下使用一个volatile关键字修饰的baseCount变量即可，单在并发场景下针对每个线程会创建一个CounterCell；最后在sumCount()方法中通过累加baseCount和CounterCell数组的counterCell值获取到Map的总大小Size，但是这个size只是一个约数，如果获取size的同时纯在插入或者删除操作，size和实际的数量可能有所不同。

[4d5e65930fd04105a8c491ee03de7c60.png]: https://img-blog.csdnimg.cn/4d5e65930fd04105a8c491ee03de7c60.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f0b6bea470784eaaa99c1c3e87ecdbb4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[935718cd34054fadb928ab56b8102e57.png]: https://img-blog.csdnimg.cn/935718cd34054fadb928ab56b8102e57.png