文档章节

ConcurrentHashMap 的 size 方法原理分析

祖冲之
 祖冲之
发布于 2018/08/01 09:27
字数 1741
阅读 32
收藏 3

ConcurrentHashMap 的 size 方法原理分析

原创: 许光明 杏仁技术站 1周前

作者 | 许光明

杏仁后端工程师。少青年程序员,关注服务端技术和农药。

前言

JAVA 语言提供了大量丰富的集合, 比如 List, Set, Map 等。其中 Map 是一个常用的一个数据结构,HashMap 是基于 Hash 算法实现 Map 接口而被广泛使用的集类。HashMap 里面是一个数组,然后数组中每个元素是一个单向链表。但是 HashMap 并不是线程安全的, 在多线程场景下使用存在并发和死循环问题。HashMap 结构如图所示:

线程安全的解决方案

线程安全的 Map 的实现有 HashTable 和 ConcurrentHashMap 等。HashTable 对集合读写操作通过 Synchronized 同步保障线程安全, 整个集合只有一把锁, 对集合的操作只能串行执行,性能不高。ConcurrentHashMap 是另一个线程安全的 Map, 通常来说他的性能优于 HashTable。 ConcurrentHashMap 的实现在 JDK1.7 和 JDK 1.8 有所不同。

在 JDK1.7 版本中,ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。简单理解就是ConcurrentHashMap 是一个 Segment 数组,Segment 通过继承 ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 Segment,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全。

JDK1.8 的实现已经摒弃了 Segment 的概念,而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现,并发控制使用 Synchronized 和 CAS 来操作,整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本。 通过 HashMap 查找的时候,根据 hash 值能够快速定位到数组的具体下标,如果发生 Hash 碰撞,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

如何计算 ConcurrentHashMap Size

由上面分析可知,ConcurrentHashMap 更适合作为线程安全的 Map。在实际的项目过程中,我们通常需要获取集合类的长度, 那么计算 ConcurrentHashMap 的元素大小就是一个有趣的问题,因为他是并发操作的,就是在你计算 size 的时候,它还在并发的插入数据,可能会导致你计算出来的 size 和你实际的 size 有差距。本文主要分析下 JDK1.8 的实现。 关于 JDK1.7 简单提一下。

在 JDK1.7 中,第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的。 第二种方案是如果第一种方案不符合,他就会给每个 Segment 加上锁,然后计算 ConcurrentHashMap 的 size 返回。其源码实现:

public int size() {
  final Segment<K,V>[] segments = this.segments;
  int size;
  boolean overflow; // true if size overflows 32 bits
  long sum;         // sum of modCounts
  long last = 0L;   // previous sum
  int retries = -1; // first iteration isn't retry
  try {
    for (;;) {
      if (retries++ == RETRIES_BEFORE_LOCK) {
        for (int j = 0; j < segments.length; ++j)
          ensureSegment(j).lock(); // force creation
      }
      sum = 0L;
      size = 0;
      overflow = false;
      for (int j = 0; j < segments.length; ++j) {
        Segment<K,V> seg = segmentAt(segments, j);
        if (seg != null) {
          sum += seg.modCount;
          int c = seg.count;
          if (c < 0 || (size += c) < 0)
            overflow = true;
        }
      }
      if (sum == last)
        break;
      last = sum;
    }
  } finally {
    if (retries > RETRIES_BEFORE_LOCK) {
      for (int j = 0; j < segments.length; ++j)
        segmentAt(segments, j).unlock();
    }
  }
  return overflow ? Integer.MAX_VALUE : size;
}

JDK1.8 实现相比 JDK 1.7 简单很多,只有一种方案,我们直接看 size() 代码:

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
           (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}

最大值是 Integer 类型的最大值,但是 Map 的 size 可能超过 MAX_VALUE, 所以还有一个方法 mappingCount(),JDK 的建议使用 mappingCount() 而不是size()mappingCount() 的代码如下:

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

以上可以看出,无论是 size() 还是 mappingCount(), 计算大小的核心方法都是 sumCount()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;
}

分析一下 sumCount() 代码。ConcurrentHashMap 提供了 baseCount、counterCells 两个辅助变量和一个 CounterCell 辅助内部类。sumCount() 就是迭代 counterCells 来统计 sum 的过程。 put 操作时,肯定会影响 size(),在 put() 方法最后会调用 addCount() 方法。

addCount() 代码如下:

  • 如果 counterCells == null, 则对 baseCount 做 CAS 自增操作。

  • 如果并发导致 baseCount CAS 失败了使用 counterCells。

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

然后,CounterCell 这个类到底是什么?我们会发现它使用了 @sun.misc.Contended 标记的类,内部包含一个 volatile 变量。@sun.misc.Contended 这个注解标识着这个类防止需要防止 "伪共享"。那么,什么又是伪共享呢?

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

CounterCell 代码如下:

@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}    

总结

 

  • JDK1.7 和 JDK1.8 对 size 的计算是不一样的。 1.7 中是先不加锁计算三次,如果三次结果不一样在加锁。

  • JDK1.8 size 是通过对 baseCount 和 counterCell 进行 CAS 计算,最终通过 baseCount 和 遍历 CounterCell 数组得出 size。

  • JDK 8 推荐使用mappingCount 方法,因为这个方法的返回值是 long 类型,不会因为 size 方法是 int 类型限制最大值。

 

全文完

 

以下文章您可能也会感兴趣:

本文转载自:https://mp.weixin.qq.com/s/JA8s-9DQ3-jNi5vXgeEJMg

共有 人打赏支持
祖冲之
粉丝 2
博文 88
码字总数 13995
作品 0
合肥
高级程序员
私信 提问
ConcurrentHashMap源码分析

前言 JDK中的Hashtable是一个线程安全的K-V形式的容器,它实现线程安全的原理十分简单,就是在所有涉及对该哈希表操作的方法上都加上了synchronized关键字,进行加锁操作。这么做实现了线程安...

Justlearn
2017/04/13
0
0
ConcurrentHashMap源码分析(JDK1.7和JDK1.8)

ConcurrentHashMap是Java中使用非常普遍的一个Map,ConcurrentHashMap较HashMap而言极大提高了并发操作速度,我们知道HashMap是线程不安全的,在多线程环境下容易出现死锁,线程安全的HashT...

申文波
2018/07/04
0
0
ConcurrentHashMap源码解析

本文主要内容 ConcurrentHashMap介绍 ConcurrentHashMap初始化 ConcurrentHashMap存储流程 ConcurrentHashMap取出流程 总结 1、ConcurrentHashMap介绍 关于Java集合类,已经介绍过很多了,今...

某昆
2018/08/18
0
0
ConcurrentHashMap分析

ConcurrentHashMap分析: 闻其名,便知其义,并发的hashmap, 我们先来看看ConcurrentHashMap数据结构图: ConcurrentHashMap由多个Segment组成,而Segment内部是由HashEntry(存放key-value对...

ihaolin
2014/03/19
0
1
Java并发学习(十九)-Java8中ConcurrentHashMap分析

断断续续看了那么些天,趁着周末把知识记下来。 在平常编程时,HashMap是用的很频繁的一个类,但是,当在并发情况下,却不推荐使用它,因为它没有做任何的并发控制,不安全,是个隐患。 当然...

anLA_
2017/12/19
0
0

没有更多内容

加载失败,请刷新页面

加载更多

使用keepalived实现nginx的高可用

概述 是这样子的,我想让家中所有的应用服务都从nginx中出去,让nginx处于访问的最边缘地带,为了让nginx可靠性加强,所以nginx就得实现高可用,分别是下面两台机器要做nginx的集群 10.10.10...

bboysoulcn
今天
1
0
Mysql索引机制B+Tree

1、问题引入 有一个用户表,为了查询的效率,需要基于id去构建索引。构建索引我们需要考虑两个方面的问题,1个是查询的效率,1个是索引数据的存储问题。该表的记录需要支持百万、千万、甚至上...

万山红遍
今天
40
0
RDD

1.概念: RDD是spark整个体系中最基础核心的概念,RDD(Resilient Distributed DataSet)即弹性分布式数据集 弹性: RDD支持横向多分区,纵向操作内存不足写入磁盘,hdfs等,实现数据在内存和...

仟昭
今天
1
0
springboot整合mycat

动态数据源项目整合 Maven依赖信息 <parent> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-parent</artifactId> <version>2.0.4.RELEASE</version> <relat......

须臾之余
今天
2
0
深入解析Vue 和微信小程序的区别、比较

写了vue项目和小程序,发现二者有许多相同之处,在此想总结一下二者的共同点和区别。 一、生命周期 先贴两张图: vue生命周期 小程序生命周期 相比之下,小程序的钩子函数要简单得多。 vue的...

前端攻城小牛
今天
9
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部