Java Concurrent Map

前言

HashMap是我们生产过程中使用较多的一个数据结构,平时非并发场景使用的HashMap,并发场景下使用的HashTable、ConcurrentHashMap。

表面的API看上去都基本是相同的,但不同的Map实现却差异较大,比如说1.6、1.17、1.8及以上版本中的HashMap、ConcurrentHashMap、远古的HashTable。在进行下面介绍之前默认大家已经理解红黑树、Hash计算等

按照顺序介绍:

Java 1.6

HashMap

默认负载因子为0.75,默认容量为16。也就是到达16*0.75 时会出发resize操作。基于数组和链表实现,这算是HashMap的一种教科书里的实现结构了(通常大学课本中特别常见),当key为null 时会添加元素至0的位置。

缺点:new HashMap时就开辟内存空间,在正式使用之前这段时间,造成了一定的内存浪费。下面是HashMap的一种实现结构

HashTable

hashTbles的实现基本可以以HashMap结构为基础,要说差异的话就是每个方法都变成了sychronized,这种直接在每个方法上直接sychronized,怕不是当时当时临时上的策略了,Collections.synchronizedMap()也是同样的粗暴。自从ConcurrentHashMap出现后已经几乎没有使用的了。

ConcurrentHashMap

1.6中的HashMap采用的是分段加锁的方式,可以简单理解为使用使用分段锁直接锁住某些段,然后减小争用的可能性(比HashTable稍微好一些),产生争用时取锁(通过reentrantlock保证并发的安全,直接继承的),来保证安全性。下面是大致的一种结构,锁的是Segment。有一个concurrency level 默认是16,也就是segment的数量,这个不可以扩容。负载因子同样是0.75,然后容量指定时是平均分配给每个桶的。

Java 1.7

HashTable的实现去查了下源码,一直到Java 10 都基本保持原始的样子。应该是停止更新了,所以以1.7 为准。

HashMap 相对于1.6中的,解决了上文提到的资源浪费问题,实现了简单的懒加载。

ConcurrentHashMap 相对于1.6 中基本没有发生变化。

Java 8

真正的变化其实发生在1.8中

HashMap:

优化点:解决碰撞过多的问题,理想情况下6和7中的实现碰撞是较少的,在底层结构看起来也就是链表的长度较短。但现实使用中并没法保证是在理想情况下或正常情况下工作的,所以经常出现链表长度很长,导致性能逐渐下降,并且有的还没开始使用,从一定角度上来说属于资源的分配不均,存在一定的浪费。针对这个问题,1.8中设定了一个阀值(8),当链表长度大于8时使用红黑树进行替换。也就是使用红黑树的方式减小碰撞所带来的代价(O(n) 到 O(logn))

然后Hash算法更改为:XORs,扩容算法更改为:ewThr<<1,然后懒加载的特性仍然保留,第一次put的时候才真正的new。

ConcurrentHashMap:

key&value都不允许为空,从1.8开始出现前置检查,并且舍弃concurrencylevel 改用动态分片。并且,这次可不是挤牙膏式更新,舍弃了之前Segment分段锁式设计,底层采用数组+链表+红黑树结构实现,采用CAS+sychronized实现并发安全。(结构基本同上面java 8中的HashMap)。

下面是putVal中的CAS+Sychronized的使用,putval也是整个ConcurrentHashMap中比较核心的,推荐详细去看一下,因为篇幅,只说里面的一两点。

具体的hash算法:

再然后取元素时,利用了类似于volatile特性的UnSafe.getObjectVolatile(),保证取到的为最新值。

1.8中的扩容方式:

当table的数量达到阀值sizeCtl时,会构建一个nextTable(大小为之前的两倍),然后把table的数据复制到nextTable中(不断的遍历原有的完成复制)。其中sizeCtl利用CAS(UnSafe.compareAndSetInt() 完成操作)可以简单看一下。1.8之前的跟之后的ConcurrentHashMap 这个过程是有所差异的,因为结构不同的关系,1.7及之前的扩容时不需要对整个map做rehash只需要对于segment做rehash就OK了

line:2432

private final voidtransfer(Node<K,V>[]tab,Node<K,V>[]nextTab) {

说一个经典的问题:

为什么要使用ConcurrentHashMap,单纯使用HashMap存在什么问题。

看上去ConcurrentHashMap相对于HashMap 也就是在一个数据操作的环节增加了锁操作变为CAS操作。这么做的意义是什么呢?

因为HashMap在并发执行put操作时会引起死循环,多线程可能会导致HashMap的Entry链表形成环形数据结构,查找时会陷入死循环。(两个线程同时扩容相撞了,导致环形链表的产生,所以悲剧就出现了——Infinite Loop)

关于rehash:

Java 6 存在rehash

Java 7 存在rehash

Java 8 可能会发生rehash,在扩充HashMap的时候,不需要像JDK1.7的实现那样重新计算hash,只需要看原来的hash值新增的那个bit是1还是0,是0的话索引没变,是1的话索引变成“原索引+oldCap”

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券