亲宝软件园·资讯

展开

concurrenthashmap的size方法原理

一粒沙cym 人气:0

concurrenthashmap的size方法原理

同上,这也是同一个面试的时候别人问的,我只是记得看过,在concurrenthashmap中会统计多次,当时就说会统计两次进行比较,人家接着问为啥。。。我傻了一下,这不是明摆着两次统计的中间有新的变化了,会导致统计不准确吗?当时也不知道说啥好,以为他有新的点,就说不知道。面试时很多问题其实冷静下来想一下,可以更进一步的,有时候其实也是怕他更进一步后下面的挖坑挖大了。

下面具体说一下这个size方法

代码就不贴了。只说原理。

众所周知,concurrenthashmap有很多歌segments,首先遍历segments将每个segment的count加起来作为整个concurrenthashMap的size。如果没有并发的情况下这自然就可以了,但这是多线程的,如果前脚统计完后脚有变化了,这就不准确了,源码中引入了,modCount和两次比较来实现size的确认。具体过程是:

1.进行第一遍遍历segments数组

将每个segemnt的count加起来作为总数,期间把每个segment的modCount加起来sum作为结果是否被修改的判断依据。

这里需要提一下modCount,这个是当segment有任何操作都会进行一次增量操作,代表的是对Segment中元素的数量造成影响的操作的次数,这个值只增不减!!!!只增不减很重要,这样就不会出现一个segment+1,导致modcount+1,而另一个segment-1,即modcount-1 ,从而在统计所有的时候modcount没有变化。

2.size操作就是遍历了两次所有的Segments

每次记录Segment的modCount值,然后将两次的modCount进行比较,如果相同,则表示期间没有发生过写入操作,就将原先遍历的结果返回,如果不相同,则把这个过程再重复做一次,如果再不相同,则就需要将所有的Segment都锁住,然后一个一个遍历了。

3.如果经判断发现两次统计出的modCount并不一致

那就如上所说,要重新启用全部segment加锁的方式来进行count的获取和统计了,这样在此期间每个segement都被锁住,无法进行其他操作,统计出的count自然很准确。

而之所以之所以要先不加锁进行判断,道理很明显,就是不希望因为size操作获取这么多锁,因为获取锁不光占用资源,也会影响其他线程对ConcurrentHash的使用,影响并发情况下程序执行的效率。使用锁要谨慎!

原理大概就是这样的,具体的代码可以去看源码,而且源码1.7和1.8有差别。。。有空再贴出来比较比较吧。

concurrenthashmap的size的思考

ConcurrentHashMap是通过分段锁来控制整个Map的安全性和并发性,那么ConcurrentHashMap在求size的时候是如何兼顾到性能以及安全性的呢?

我们首先会想到以下两种方法

1.获取所有的Segment锁。

这个方法是可行的,但是这会导致并发性能变差,因为你获取了所有的锁,那么别的线程将无法对该HashMap执行任何操作。

2.逐个地获取Segment。

这种方法也有问题,有可能在后面获取下一个Segment里面的元素的个数的时候,上面一个Segment里面元素的个数已经很可能改变了,因此最后累加到最后,有可能数据是错误的。

那么ConcurrentHashMap采用的是什么措施呢。源码如下所示:

java1.7以前的源码:

由于在累加count的操作的过程中之前累加过的count发生变化的几率非常小,所以ConcurrentHashMap先尝试2次不锁住Segment的方式来统计每个Segment的大小,如果在统计的过程中Segment的count发生了变化,这时候再加锁统计Segment的count。

java1.7以及1,7以后的源码:

取size的核心是sumCount函数。

    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;
            }
        }
        return sum;
    }

核心逻辑:当 counterCells 不是 null,就遍历元素,并和 baseCount 累加。

查看两个属性:baseCount 和 counterCells。

先看 baseCount

private transient volatile long baseCount;

baseCount是一个 volatile 的变量,在 addCount 方法中会使用它,而 addCount 方法在 put 结束后会调用。在 addCount 方法中,会对这个变量做 CAS 加法。

  private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        if ((as = counterCells) != null ||
            !U.compareAndSetLong(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.compareAndSetLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x, uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }

但是如果并发导致 CAS 失败了,怎么办呢?使用 counterCells。

如果上面 CAS 失败了,在 fullAddCount 方法中,会继续死循环操作,直到成功。

最后,再来看一下counterCells这个类。

    @jdk.internal.vm.annotation.Contended static final class CounterCell {
        volatile long value;
        CounterCell(long x) { value = x; }
    }

上述源码中的注释是为了避免伪共享(false sharing)。

先引用个伪共享的解释: 缓存系统中是以缓存行(cache line)为单位存储的。

缓存行是2的整数幂个连续字节, 一般为32-256个字节。最常见的缓存行大小是64个字节。

当多线程修改互相独立的变量时, 如果这些变量共享同一个缓存行,就会无意中影响彼此的性能,这就是伪共享。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。

加载全部内容

相关教程
猜你喜欢
用户评论