ConcurrentHashMap

  • Post author:
  • Post category:其他




1.ConcurrentHashMap底层实现



1.1 JDK1.7

在这里插入图片描述


底层数据结构:Segments数组+HashEntry数组+链表,采用分段锁保证安全性

一个ConcurrentHashMap中有一个Segments数组,一个Segments中存储一个HashEntry数组,每个HashEntry是一个链表结构的元素。

segment继承自ReentrantLock锁。

首先将数据分为一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一段数据时,其他段的数据也能被其他线程访问,实现了真正的并发访问。


1.1.1、ConcurrentHashMap有参构造函数初始化



1、必要参数校验。

2、校验并发级别 concurrencyLevel 大小,如果大于最大值,重置为最大值。无参构造默认值是 16.

3、寻找并发级别 concurrencyLevel 之上最近的 2 的幂次方值,作为初始化容量大小,默认是 16。

4、记录 segmentShift 偏移量,这个值为【容量 = 2 的N次方】中的 N,在后面 Put 时计算位置时会用到。默认是 32 – sshift = 28.

5、记录 segmentMask,默认是 ssize – 1 = 16 -1 = 15.

6、初始化 segments[0],默认大小为 2,负载因子 0.75,扩容阀值是 2*0.75=1.5,插入第二个值时才会进行扩容。


1.1.2、put方法流程:



1)计算要 put 的 key 的位置,获取指定位置的 Segment。


2)如果指定位置的 Segment 为空,则初始化这个 Segment。


初始化 Segment 流程:

检查计算得到的位置的 Segment 是否为null.

为 null 继续初始化,使用 Segment[0] 的容量和负载因子创建一个 HashEntry 数组。

再次检查计算得到的指定位置的 Segment 是否为null.

使用创建的 HashEntry 数组初始化这个 Segment.

自旋判断计算得到的指定位置的 Segment 是否为null,使用 CAS 在这个位置赋值为 Segment.


3)Segment.put 插入 key,value 值


由于 Segment 继承了 ReentrantLock,所以 Segment 内部可以很方便的获取锁,put 流程就用到了这个功能。

1、tryLock() 获取锁,获取不到使用 scanAndLockForPut 方法继续获取。

【scanAndLockForPut 方法】:

这个方法做的操作就是不断的自旋 tryLock() 获取锁。当自旋次数大于指定次数时,使用 lock() 阻塞获取锁。在自旋时顺表获取下 hash 位置的 HashEntry。

2、计算 put 的数据要放入的 index 位置,然后获取这个位置上的 HashEntry 。

3、遍历 put 新元素,为什么要遍历?因为这里获取的 HashEntry 可能是一个空元素,也可能是链表已存在,所以要区别对待。

如果这个位置上的 HashEntry 不存在:

1)如果当前容量大于扩容阀值,小于最大容量,进行扩容。

2)直接头插法插入。

如果这个位置上的 HashEntry 存在:

1)判断链表当前元素 Key 和 hash 值是否和要 put 的 key 和 hash 值一致。一致则替换值

2)不一致,获取链表下一个节点,直到发现相同进行值替换,或者链表表里完毕没有相同的。

如果当前容量大于扩容阀值,小于最大容量,进行扩容。

直接链表头插法插入。

4、如果要插入的位置之前已经存在,替换后返回旧值,否则返回 null.


1.1.3 get方法流程:

HashEntry中的value属性和next指针是用volatile修饰的,保证了可见性,所以每次获取的都是最新值,get过程不需要加锁。

1.将key传入get方法中,先根据key的hashcode的值找到对应的segment段。

2.再根据segment中的get方法再次hash,找到HashEntry数组中的位置。

3.最后在链表中根据hash值和equals方法进行查找。

ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null。


1.1.4 扩容 rehash


ConcurrentHashMap 的扩容只会扩容到原来的两倍。老数组里的数据移动到新的数组时,位置要么不变,要么变为 index+ oldSize,参数里的 node 会在扩容之后使用链表头插法插入到指定位置。



1.2 JDK1.8


底层数据结构

:Node数组+链表+红黑树 采用

Synchronized和CAS

来保证线程安全。


初始化

:当数组为空时,通过对变量 sizeCtl的值进行判断,如果小于0,说明另外的线程执行CAS 成功,正在进行初始化,当前线程会主动让出CPU;如果大于0,会通过自旋和 CAS 操作去实现数组的初始化。


put方法



1、如果key或value为空,则抛出空指针异常;

2、根据 key 计算出 hashcode 。

3、判断Node数组有没有初始化,如果没有初始化先通过自旋+CAS的方式初始化initTable()方法;

4、找到Node数组中的位置,如果不存在hash冲突,即该位置是null,利用 CAS 尝试写入,失败则自旋保证成功。

5、如果当前位置的 hashcode == MOVED == -1,则需要进行扩容操作。

6、如果上述步骤3、4、5都不满足,就先对链表的头节点或者红黑树的头节点加synchronized锁,写入数据。

6.1)如果是链表,就遍历链表,如果key相同就执行覆盖操作,如果不同就将元素插入到链表的尾部,

如果数量大于 TREEIFY_THRESHOLD 则要执行树化方法,在treeifyBin中会首先判断当前数组长度≥64时才会将链表转换为红黑树。

6.2)如果是红黑树,就按照红黑树的结构进行插入。


get方法


get操作全程无锁。get操作可以无锁是由于Node元素的val和指针next是用volatile修饰的。

在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。

1.根据 hash 值计算位置。

2.查找到指定位置,如果头节点就是要找的,直接返回它的 value.

3.如果头节点 hash 值小于 0 ,说明正在扩容或者是红黑树,使用红黑树的查找方式进行查找。

4、如果是链表节点,通过遍历链表进行查找。



2、ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。

1、

底层数据结构





ConcurrentHashMap

: JDK1.7 的 ConcurrentHashMap 底层采用 分段的数组+链表 实现,JDK1.8 采用的数据结构跟 HashMap1.8 的结构一样,Node数组+链表/红黑二叉树。



Hashtable

: Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式,数组是 HashMap 的主体,链表则是主要为了解决哈希冲突而存在的;

2、实现线程安全的方式(重要):



ConcurrentHashMap

: 在 JDK1.7 的时候,ConcurrentHashMap(分段锁) 对整个桶数组进行了分割分段(Segment),每一把锁只锁容器其中一部分数据,多线程访问容器里不同数据段的数据,就不会存在锁竞争,提高并发访问率。 到了 JDK1.8 的时候已经摒弃了 Segment 的概念,而是直接用 Node 数组+链表+红黑树的数据结构来实现,并发控制使用 synchronized 和 CAS 来操作。(JDK1.6 以后 对 synchronized 锁做了很多优化) 整个看起来就像是优化过且线程安全的 HashMap,虽然在 JDK1.8 中还能看到 Segment 的数据结构,但是已经简化了属性,只是为了兼容旧版本;



Hashtable

(同一把锁) :使用 synchronized 来保证线程安全,效率非常低下。当一个线程访问同步方法时,其他线程也访问同步方法,可能会进入阻塞或轮询状态,如使用 put 添加元素,另一个线程不能使用 put 添加元素,也不能使用 get,竞争会越来越激烈效率越低。



3、ConcurrentHashMap或Hashtable不支持key或value为null的原因

因为

ConcurrentHashmap和Hashtable都是支持并发

的,这样会有一个问题,

当你通过get(k)获取对应的value时,如果获取到的是null时,你无法判断,它是put(k,v)的时候value为null,还是这个key从来没有做过映射

。HashMap是非并发的,可以通过contains(key)来做这个判断。而

支持并发的Map在调用m.contains(key)和m.get(key)时,m可能已经不同了



4、JDK1.8中为什么使用synchronized替换可重入锁ReentrantLock?

Segment继承了ReentrantLock,所以Segment是一种可重入锁。

1.Segment可重入锁锁住的是一个HashEntry数组,synchronized锁住的只是发生hash冲突的链表的头节点或红黑树的节点,

提高了并发性能

2.从JDK1.6开始,

对 synchronized 锁的实现引入了大量的优化

,并且 synchronized 有多种锁状态,会从偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

只要并发的线程可以在一定次数的自旋内拿到锁(偏向锁不用自旋),那么synchronized就不会升级为重量级锁,等待的线程也不会被挂起,

减少了线程挂起和唤醒的切换的过程开销


而ReentrantLock不会自旋,会直接挂起,这样一来就很容易会多出线程上下文开销的代价。

3.

减少内存开销

。假设使用可重入锁来获得同步支持,那么每个节点都需要通过继承 AQS 来获得同步支持。

但并不是每个节点都需要获得同步支持的,只有链表的头节点(红黑树的根节点)需要同步,这无疑带来了巨大内存浪费。



5、多线程下安全的操作Map还有其他方法吗?

在这里插入图片描述



6、ConcurrentHashMap和Hashtable的效率哪个更高?

在这里插入图片描述



7、ConcurrentHashMap的get方法是否要加锁?

在这里插入图片描述



版权声明:本文为zqmk531933288原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。