11、ConcurrentHashMap如何计算Size

一、前言

我们都知道,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。
&nbsp;

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)无线程竞争时:
&nbsp;

2)有线程竞争CAS修改同一counterCells下标位置的值:
&nbsp;

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和实际的数量可能有所不同。