搜公众号
推荐 原创 视频 Java开发 开发工具 Python开发 Kotlin开发 Ruby开发 .NET开发 服务器运维 开放平台 架构师 大数据 云计算 人工智能 开发语言 其它开发 iOS开发 前端开发 JavaScript开发 Android开发 PHP开发 数据库
Lambda在线 > java进阶笔记 > 1.7&1.8-ConcurrentHashMap对比

1.7&1.8-ConcurrentHashMap对比

java进阶笔记 2019-02-13
举报

导语:前文写了关于1.7ConcurrentHashMap原理的简单分析,本次针对1.8版本的升级,对数据结构和使用方式进行简单对比,梳理了一些质量不错的网络博客,对比数据结构、寻址方式、扩容方式,1.8进行了较大的改变,明显提升了效率。




Java 7基于分段锁的ConcurrentHashMap

注:本章的代码均基于JDK 1.7.0_67

数据结构

Java 7中的ConcurrentHashMap的底层数据结构仍然是数组和链表。与HashMap不同的是,ConcurrentHashMap最外层不是一个大的数组,而是一个Segment的数组。每个Segment包含一个与HashMap数据结构差不多的链表数组。整体数据结构如下图所示。 JAVA 7 ConcurrentHashMap

寻址方式

在读写某个Key时,先取该Key的哈希值。并将哈希值的高N位对Segment个数取模从而得到该Key应该属于哪个Segment,接着如同操作HashMap一样操作这个Segment。为了保证不同的值均匀分布到不同的Segment,需要通过如下方法计算哈希值。

  
    
    
  
  1. private int hash(Object k) {

  2.  int h = hashSeed;

  3.  if ((0 != h) && (k instanceof String)) {

  4.    return sun.misc.Hashing.stringHash32((String) k);

  5.  }

  6.  h ^= k.hashCode();

  7.  h += (h <<  15) ^ 0xffffcd7d;

  8.  h ^= (h >>> 10);

  9.  h += (h <<   3);

  10.  h ^= (h >>>  6);

  11.  h += (h <<   2) + (h << 14);

  12.  return h ^ (h >>> 16);

  13. }

同样为了提高取模运算效率,通过如下计算,ssize即为大于concurrencyLevel的最小的2的N次方,同时segmentMask为2^N-1。这一点跟上文中计算数组长度的方法一致。对于某一个Key的哈希值,只需要向右移segmentShift位以取高sshift位,再与segmentMask取与操作即可得到它在Segment数组上的索引。

  
    
    
  
  1. int sshift = 0;

  2. int ssize = 1;

  3. while (ssize < concurrencyLevel) {

  4.  ++sshift;

  5.  ssize <<= 1;

  6. }

  7. this.segmentShift = 32 - sshift;

  8. this.segmentMask = ssize - 1;

  9. Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];

同步方式

Segment继承自ReentrantLock,所以我们可以很方便的对每一个Segment上锁。

对于读操作,获取Key所在的Segment时,需要保证可见性(请参考如何保证多线程条件下的可见性)。具体实现上可以使用volatile关键字,也可使用锁。但使用锁开销太大,而使用volatile时每次写操作都会让所有CPU内缓存无效,也有一定开销。ConcurrentHashMap使用如下方法保证可见性,取得最新的Segment。

  
    
    
  
  1. Segment<K,V> s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)

获取Segment中的HashEntry时也使用了类似方法

  
    
    
  
  1. HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile

  2.  (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE)

对于写操作,并不要求同时获取所有Segment的锁,因为那样相当于锁住了整个Map。它会先获取该Key-Value对所在的Segment的锁,获取成功后就可以像操作一个普通的HashMap一样操作该Segment,并保证该Segment的安全性。 同时由于其它Segment的锁并未被获取,因此理论上可支持concurrencyLevel(等于Segment的个数)个线程安全的并发读写。

获取锁时,并不直接使用lock来获取,因为该方法获取锁失败时会挂起(参考可重入锁)。事实上,它使用了自旋锁,如果tryLock获取锁失败,说明锁被其它线程占用,此时通过循环再次以tryLock的方式申请锁。如果在循环过程中该Key所对应的链表头被修改,则重置retry次数。如果retry次数超过一定值,则使用lock方法申请锁。

这里使用自旋锁是因为自旋锁的效率比较高,但是它消耗CPU资源比较多,因此在自旋次数超过阈值时切换为互斥锁。

size操作

put、remove和get操作只需要关心一个Segment,而size操作需要遍历所有的Segment才能算出整个Map的大小。一个简单的方案是,先锁住所有Sgment,计算完后再解锁。但这样做,在做size操作时,不仅无法对Map进行写操作,同时也无法进行读操作,不利于对Map的并行操作。

为更好支持并发操作,ConcurrentHashMap会在不上锁的前提逐个Segment计算3次size,如果某相邻两次计算获取的所有Segment的更新次数(每个Segment都与HashMap一样通过modCount跟踪自己的修改次数,Segment每修改一次其modCount加一)相等,说明这两次计算过程中无更新操作,则这两次计算出的总size相等,可直接作为最终结果返回。如果这三次计算过程中Map有更新,则对所有Segment加锁重新计算Size。该计算方法代码如下

  
    
    
  
  1. public int size() {

  2.  final Segment<K,V>[] segments = this.segments;

  3.  int size;

  4.  boolean overflow; // true if size overflows 32 bits

  5.  long sum;         // sum of modCounts

  6.  long last = 0L;   // previous sum

  7.  int retries = -1; // first iteration isn't retry

  8.  try {

  9.    for (;;) {

  10.      if (retries++ == RETRIES_BEFORE_LOCK) {

  11.        for (int j = 0; j < segments.length; ++j)

  12.          ensureSegment(j).lock(); // force creation

  13.      }

  14.      sum = 0L;

  15.      size = 0;

  16.      overflow = false;

  17.      for (int j = 0; j < segments.length; ++j) {

  18.        Segment<K,V> seg = segmentAt(segments, j);

  19.        if (seg != null) {

  20.          sum += seg.modCount;

  21.          int c = seg.count;

  22.          if (c < 0 || (size += c) < 0)

  23.            overflow = true;

  24.        }

  25.      }

  26.      if (sum == last)

  27.        break;

  28.      last = sum;

  29.    }

  30.  } finally {

  31.    if (retries > RETRIES_BEFORE_LOCK) {

  32.      for (int j = 0; j < segments.length; ++j)

  33.        segmentAt(segments, j).unlock();

  34.    }

  35.  }

  36.  return overflow ? Integer.MAX_VALUE : size;

  37. }

不同之处

ConcurrentHashMap与HashMap相比,有以下不同点

ConcurrentHashMap线程安全,而HashMap非线程安全 HashMap允许Key和Value为null,而ConcurrentHashMap不允许 HashMap不允许通过Iterator遍历的同时通过HashMap修改,而ConcurrentHashMap允许该行为,并且该更新对后续的遍历可见

Java 8基于CAS的ConcurrentHashMap

注:本章的代码均基于JDK 1.8.0_111

数据结构

Java 7为实现并行访问,引入了Segment这一结构,实现了分段锁,理论上最大并发度与Segment个数相等。Java 8为进一步提高并发性,摒弃了分段锁的方案,而是直接使用一个大的数组。同时为了提高哈希碰撞下的寻址性能,Java 8在链表长度超过一定阈值(8)时将链表(寻址时间复杂度为O(N))转换为红黑树(寻址时间复杂度为O(long(N)))。其数据结构如下图所示

JAVA 8 ConcurrentHashMap

寻址方式

Java 8的ConcurrentHashMap同样是通过Key的哈希值与数组长度取模确定该Key在数组中的索引。同样为了避免不太好的Key的hashCode设计,它通过如下方法计算得到Key的最终哈希值。不同的是,Java 8的ConcurrentHashMap作者认为引入红黑树后,即使哈希冲突比较严重,寻址效率也足够高,所以作者并未在哈希值的计算上做过多设计,只是将Key的hashCode值与其高16位作异或并保证最高位为0(从而保证最终结果为正整数)。

  
    
    
  
  1. static final int spread(int h) {

  2.  return (h ^ (h >>> 16)) & HASH_BITS;

  3. }

同步方式

对于put操作,如果Key对应的数组元素为null,则通过CAS操作将其设置为当前值。如果Key对应的数组元素(也即链表表头或者树的根元素)不为null,则对该元素使用synchronized关键字申请锁,然后进行操作。如果该put操作使得当前链表长度超过一定阈值,则将该链表转换为树,从而提高寻址效率。

对于读操作,由于数组被volatile关键字修饰,因此不用担心数组的可见性问题。同时每个元素是一个Node实例(Java 7中每个元素是一个HashEntry),它的Key值和hash值都由final修饰,不可变更,无须关心它们被修改后的可见性问题。而其Value及对下一个元素的引用由volatile修饰,可见性也有保障。

  
    
    
  
  1. static class Node<K,V> implements Map.Entry<K,V> {

  2.  final int hash;

  3.  final K key;

  4.  volatile V val;

  5.  volatile Node<K,V> next;

  6. }

对于Key对应的数组元素的可见性,由Unsafe的getObjectVolatile方法保证。

  
    
    
  
  1. static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {

  2.  return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);

  3. }

size操作

put方法和remove方法都会通过addCount方法维护Map的size。size方法通过sumCount获取由addCount方法维护的Map的size。

推荐阅读






如果你喜欢本文,请长按二维码关注
java进阶笔记

为更优秀的你


java技术交流群

希望你和更多人一起进步

java交流群

为更优秀的你





版权声明:本站内容全部来自于腾讯微信公众号,属第三方自助推荐收录。《1.7&1.8-ConcurrentHashMap对比》的版权归原作者「java进阶笔记」所有,文章言论观点不代表Lambda在线的观点, Lambda在线不承担任何法律责任。如需删除可联系QQ:516101458

文章来源: 阅读原文

相关阅读

关注java进阶笔记微信公众号

java进阶笔记微信公众号:tangshandxs

java进阶笔记

手机扫描上方二维码即可关注java进阶笔记微信公众号

java进阶笔记最新文章

精品公众号随机推荐

举报