C/C++教程

高薪程序员&面试题精讲系列52之ConcurrentHashMap怎么统计大小?读操作需不需要加锁?

本文主要是介绍高薪程序员&面试题精讲系列52之ConcurrentHashMap怎么统计大小?读操作需不需要加锁?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. 今日面试题

ConcurrentHashMap的底层原理是什么?

你知道ConcurrentHashMap是怎么统计大小的?

ConcurrentHashMap的读操作为什么不需要加锁?

.......

2. 题目剖析

壹哥在前面4篇文章中,给大家介绍了ConcurrentHashMap的通用功能、特点,以及JDK 7、8中ConcurrentHashMap的底层数据结构,还有ConcurrentHashMap中的核心属性等内容,文章链接如下:

高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗?

高薪程序员&面试题精讲系列46之说说JDK7中ConcurrentHashMap的底层原理,有哪些数据结构

高薪程序员&面试题精讲系列47之说说JDK8中ConcurrentHashMap的底层原理,HashMap与ConcurrentHashMap有什么区别?

高薪程序员&面试题精讲系列48之说说JDK8中ConcurrentHashMap的sizeCtl是什么意思?最大容量、负载因子是多少?

高薪程序员&面试题精讲系列49之说说ConcurrentHashMap#put方法的源码及数据添加流程

从本文开始,壹哥给大家重点分析JDK 8中ConcurrentHashMap#size()方法的源码,重点讲解ConcurrentHashMap是如何进行统计集合中元素数量的,这一块也是咱们面试时的高频考点。

二. size()计算方法实现详解

1. size计算容量方法

分析完了以上这些重要的源码之后,面试官有时候还会问我们如何计算ConcurrentHashMap中到底存了多少条数据。对于ConcurrentHashMap来说,这个table里到底装了多少个数据元素,其实是个不确定的数量。因为我们不可能在调用size()方法的时候,像GC的“stop the world”一样让其他线程都停下来让你去统计,因此只能说这个数量是个估计值。对于这个估计值,ConcurrentHashMap也是大费周章才计算出来的。

2. 辅助定义

为了统计内部存储的元素个数,ConcurrentHashMap定义了一些变量和一个内部类。

/**
* A padded cell for distributing counts.  Adapted from LongAdder
* and Striped64.  See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { 
        value = x; 
    }
}

/**
* 实际上保存的是hashmap中的元素个数,利用CAS锁进行更新。但它并不用返回当前hashmap的元素个数 
*/
private transient volatile long baseCount;
    
/**
* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
*/
private transient volatile int cellsBusy;

/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;

3. mappingCount与size方法

size()方法的作用是为我们返回哈希表中实际存在的键值对总数,mappingCount()方法与size()方法类似。 从Java工程师给出的注释来看,应该使用mappingCount代替size方法。但这两个方法都没有直接返回basecount,而是统计一个值,而这个值其实也是一个大概的数值,因此可能在统计的时候有其他线程正在执行插入或删除操作。

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n);
}
    
public long mappingCount() {
        long n = sumCount();
        return (n < 0L) ? 0L : n; // ignore transient negative values
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;//所有counter的值求和
        }
    }
    return sum;
}

我们会发现,无论是size()方法还是mappingCount()方法,内部都是在调用sumCount()方法,该方法的代码其实也并不复杂,其内部使用的算法其实是如下算法:

总的来说,ConcurrentHashMap的计数主要是延用了分段计数的思路

另外可能你还会有疑问,ConcurrentHashMap 中的 baseCount 属性,不就是记录了所有键值对的总数吗?直接返回它不就行了吗?

之所以没有这么做,是因为ConcurrentHashMap中的 addCount() 方法用于 通过CAS来更新 baseCount,但有可能在高并发的情况下更新失败,即这些节点虽然已经被添加到哈希表中了,但数量却没有被统计。

addCount 方法在更新 baseCount 失败时,会调用 fullAddCount()方法 将这些失败的结点包装成一个 CounterCell 对象,保存在 CounterCell 数组中。那么整张表实际的 size,其实是 baseCount 加上 CounterCell 数组中元素的个数。

4. addCount方法

在put()方法结尾处调用了addCount方法,该方法会把当前ConcurrentHashMap的元素个数+1。这个方法一共做了两件事:更新baseCount的值,检测是否进行扩容。该方法的源码如下:

private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        //利用CAS方法更新baseCount的值 
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x,uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        
        //如果check值大于等于0 则需要检验是否需要进行扩容操作
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            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);
                }
                
				//当前线程是唯一的或是第一个发起扩容的线程  此时nextTable=null
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
    }
}

最后我们总结一下,ConcurrentHashMap统计容器大小其实是用了两种思路:

CAS方式直接递增:在线程竞争不大的时候,直接使用CAS操作递增baseCount值,这里说的竞争不大指的是CAS操作不会失败的情况;

分而治之的桶计数:若出现了CAS操作失败的情况,则证明此时有线程竞争了,计数方式从CAS方式转变为分而治之的桶计数方式。

三. 为什么ConcurrentHashMap的读操作不需要加锁?

1. 简述

我们知道ConcurrentHashMap(JDK 8)是一个并发集合,所以是线程安全的。但当我们阅读源码中的get()方法时,会发现get()方法是没有添加任何锁的。所以我们想知道,get操作为什么不需要加锁呢?

实际上在JDK 8中,ConcurrentHashMap的get()方法之所以不需要加锁,主要是因为相关变量都加上了volatile修饰符,所以get操作自身几乎无需考虑线程安全性和变量可见性,只需要注意原子性即可。

这里的原子性,指的是get操作时被多个线程共享的table变量及节点属性,这些变量可能会被其他线程修改,所以需要一开始就把它们保存到局部变量中,然后再使用,这样就不必担心有其他线程修改了。

2. volatile的作用

普通的成员变量不能保证线程间的可见性。因为普通成员变量被修改之后,什么时候被写入主内存是不确定的。而当其他线程去读取时,此时内存中可能还是原来的旧值,因此无法保证可见性。

所以此时我们可以使用Java提供的volatile关键字,来保证线程间变量的可见性、有序性,一旦某个变量添加了volatile关键字,它就成了一个共享变量,但它不能保证原子性。volatile作用如下:

  • volatile关键字可以保证对基本类型变量的修改,在多个线程中的读操作保持一致。但对于引用类型如数组,实体bean,仅仅保证引用的可见性,但并不保证引用内容的可见性。
  • 禁止进行指令重排序。

为了提高处理速度,CPU处理器不会直接和内存进行通信,而是先将系统内存中的数据读到内部缓存(L1,L2或其他)后再进行操作,但操作完不知道何时会写到内存。

如果某个线程对声明了volatile的变量进行写操作,JVM就会向处理器发送一条指令,将这个变量所在的内存缓存写回到系统内存中。

但是就算写回到了系统内存,如果其他处理器缓存的值还是旧的,再执行计算操作就会有问题。

所以在多处理器环境下,为了保证各个处理器的缓存结果是一致的,就需要实现 缓存一致性协议

当某个CPU在写数据时,如果发现操作的变量是共享变量,则会通知其他CPU,告知该变量的缓存行是无效的。因此其他CPU在读取该变量时,如果发现其无效,则会重新从主内存中加载数据。

3. get()不加锁原因

最后我们再梳理一下get操作不加锁的原因。

  • 使用volatile关键字,会强制将修改后的值立即写入主内存;
  • 当线程2进行变量修改时,volatile可以使得线程1所在工作内存中缓存变量的缓存行无效(反映到硬件层的话,就是CPU的L1或者L2缓存中对应的缓存行无效);
  • 由于线程1的工作内存中缓存变量的缓存行无效,所以当线程1再次读取该变量的值时会去主内存重新读取;
  • 所以get()操作全程不需要加锁,是因为Node类的成员变量val,是用volatile关键字来修饰的,和table数组用volatile修饰是没有关系的。

四. 结语

最后,壹哥 再把两个版本中的ConcurrentHashMap进行一个简单总结。

1. JDK 7的ConcurrentHashMap小结

  • JDK 7中的ConcurrentHashMap,当长度过长时,碰撞会很频繁的发生,链表的增改删查操作都会消耗很长的时间,影响性能。
  • JDK 7中的ConcurrentHashMap主要使用Segment分段锁来实现并发控制,把Map分割成若干个Segment。在put()时需要锁住Segment,get()时候不需要加锁,使用volatile来保证可见性。
  • 当统计全局数量时(比如size),首先会尝试多次计算modCount来确定。这几次尝试时,会判断是否有其他线程进行了修改操作,如果没有,则直接返回size;如果有,则需要依次锁住所有的Segment来计算。

2. JDK 8的ConcurrentHashMap小结

  • 不采用Segment而是采用Node,减小了锁的粒度;
  • 设计了MOVED状态,在resize过程中,线程2还在put数据时,线程1会帮助resize;
  • 使用3个CAS操作来确保Node中的一些原子性操作,这种方式代替了锁;
  • sizeCtl的不同值代表了不同含义,起到了控制的作用;
  • 使用synchronized而不是ReentrantLock。

五. 结语

至此,壹哥 用了几万字,终于带各位认真的研究了一遍ConcurrentHashMap,尤其是其底层原理和源码,不知道你现在对ConcurrentHashMap是否有了足够的了解呢?如果还有什么疑问,可以给壹哥留言评论哦!

这篇关于高薪程序员&面试题精讲系列52之ConcurrentHashMap怎么统计大小?读操作需不需要加锁?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!