今天看了下ConcurrentHashMap的实现源码,下面总结一下,只为自己加强记忆,如果想看详细讲解可以参考文章:https://blog.csdn.net/qq296398300/article/details/79074239
个人总结:
在jdk1.7中:
ConcurrentHashMap是由Segment数组和多个HashEntry数组组成,Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁,也就是上面的提到的锁分离技术,而每一个Segment元素存储的是HashEntry数组+链表,这个和HashMap的数据存储结构一样 。
put操作:对于ConcurrentHashMap的数据插入,这里要进行两次Hash去定位数据的存储位置
static class Segment<K,V> extends ReentrantLock implements Serializable {
从上Segment的继承体系可以看出,Segment实现了ReentrantLock,也就带有锁的功能,当执行put操作时,会进行第一次key的hash来定位Segment的位置,如果该Segment还没有初始化,即通过CAS操作进行赋值,然后进行第二次hash操作,找到相应的HashEntry的位置,这里会利用继承过来的锁的特性,在将数据插入指定的HashEntry位置时(链表的尾端),会通过继承ReentrantLock的tryLock()方法尝试去获取锁,如果获取成功就直接插入相应的位置,如果已经有线程获取该Segment的锁,那当前线程会以自旋的方式去继续的调用tryLock()方法去获取锁,超过指定次数就挂起,等待唤醒.
get操作: ConcurrentHashMap的get操作跟HashMap类似,只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置,然后再hash定位到指定的HashEntry,遍历该HashEntry下的链表进行对比,成功就返回,不成功就返回null 。
size操作: 计算ConcurrentHashMap的元素大小是一个有趣的问题,因为他是并发操作的,就是在你计算size的时候,他还在并发的插入数据,可能会导致你计算出来的size和你实际的size有相差(在你return size的时候,插入了多个数据),要解决这个问题,JDK1.7版本用两种方案 :
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(); } }
1.第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size,最多三次,比较前后两次计算的结果,结果一致就认为当前没有元素加入,计算的结果是准确的 2.第二种方案是如果第一种方案不符合,他就会给每个Segment加上锁,然后计算ConcurrentHashMap的size返回。
在jdk1.8中:
JDK1.8的实现已经摒弃了Segment的概念,而是直接用Node数组+链表+红黑树的数据结构来实现,并发控制使用Synchronized和CAS来操作,整个看起来就像是优化过且线程安全的HashMap,虽然在JDK1.8中还能看到Segment的数据结构,但是已经简化了属性,只是为了兼容旧版本。
ConcurrentHashMap的初始化其实是一个空实现,并没有做任何事,这里后面会讲到,这也是和其他的集合类有区别的地方,初始化操作并不是在构造函数实现的,而是在put操作中实现。
put操作:
public V put(K key, V value) { return putVal(key, value, false); } /** Implementation for put and putIfAbsent */ final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); //两次hash,减少hash冲突,可以均匀分布 int binCount = 0; for (Node<K,V>[] tab = table;;) { //对这个table进行迭代 Node<K,V> f; int n, i, fh; //这里就是上面构造方法没有进行初始化,在这里进行判断,为null就调用initTable进行初始化,属于懒汉模式初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {//如果i位置没有数据,就直接无锁插入 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED)//如果在进行扩容,则先进行扩容操作 tab = helpTransfer(tab, f); else { V oldVal = null; //如果以上条件都不满足,那就要进行加锁操作,也就是存在hash冲突,锁住链表或者红黑树的头结点 synchronized (f) { if (tabAt(tab, i) == f) { if (fh >= 0) { //表示该节点是链表结构 binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; //这里涉及到相同的key进行put就会覆盖原先的value if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { //插入链表尾部 pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) {//红黑树结构 Node<K,V> p; binCount = 2; //红黑树结构旋转插入 if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } addCount(1L, binCount);//统计size,并且检查是否需要扩容 return null; }
这个put的过程很清晰,对当前的table进行无条件自循环直到put成功,可以分成以下六步流程来概述
1.如果没有初始化就先调用initTable()方法来进行初始化过程
2.如果没有hash冲突就直接CAS插入
3.如果还在进行扩容操作就先进行扩容
4.如果存在hash冲突,就加锁来保证线程安全,这里有两种情况,一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入
5.最后一个如果该链表的数量大于阈值8,就要先转换成黑红树的结构,break再一次进入循环
6.如果添加成功就调用addCount()方法统计size,并且检查是否需要扩容
get操作:
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; int h = spread(key.hashCode()); //计算两次hash if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {//读取首节点的Node元素 if ((eh = e.hash) == h) { //如果该节点就是首节点就返回 if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } //hash值为负值表示正在扩容,这个时候查的是ForwardingNode的find方法来定位到nextTable来 //查找,查找到就返回 else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; while ((e = e.next) != null) {//既不是首节点也不是ForwardingNode,那就往下遍历 if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; }
流程很简单,也很清晰,可以分为三个步骤来描述
1.计算hash值,定位到该table索引位置,如果是首节点符合就返回
2.如果遇到扩容的时候,会调用标志正在扩容节点ForwardingNode的find方法,查找该节点,匹配就返回
3.以上都不符合的话,就往下遍历节点,匹配就返回,否则最后就返回null
总结与思考
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap,相对而言,ConcurrentHashMap只是增加了同步的操作来控制并发,从JDK1.7版本的ReentrantLock+Segment+HashEntry,到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言,总结如下思考
1.JDK1.8的实现降低锁的粒度,JDK1.7版本锁的粒度是基于Segment的,包含多个HashEntry,而JDK1.8锁的粒度就是HashEntry(首节点)
2.JDK1.8版本的数据结构变得更加简单,使得操作也更加清晰流畅,因为已经使用synchronized来进行同步,所以不需要分段锁的概念,也就不需要Segment这种数据结构了,由于粒度的降低,实现的复杂度也增加了 3.JDK1.8使用红黑树来优化链表,基于长度很长的链表的遍历是一个很漫长的过程,而红黑树的遍历效率是很快的,代替一定阈值的链表,这样形成一个最佳拍档
4.JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock,我觉得有以下几点
1.因为粒度降低了,在相对而言的低粒度加锁方式,synchronized并不比ReentrantLock差,在粗粒度加锁中 ReentrantLock可能通过Condition来控制各个低粒度的边界,更加的灵活,而在低粒度中,Condition的优 势就没有了
2.JVM的开发团队从来都没有放弃synchronized,而且基于JVM的synchronized优化空间更大,使用内嵌的 关键字比使用API更加自然
3.在大量的数据操作下,对于JVM的内存压力,基于API的ReentrantLock会开销更多的内存,虽然不是瓶 颈,但是也是一个选择依据
相关推荐
ConcurrentHashMap的实现原理(JDK1.7和JDK1.8),并说明了在jdk1.7与jdk1.8的不同实现原理
哈希表就是一种以 键-值(key-indexed) 存储数据的结构,我们只要输入待查 找的值即 key,即可查找到其对应的值。 哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数 组来实现:将键作为索引...
jdk1.8新特性 java语言有哪些优点? 同一个.java文件中是否可以有多个main方法 一个".java"源文件中是否可以包括多个类(不是内部类)?有什么限制? 如何在main方法执行前输出”hello world” java程序的初始化顺序 ...
jdk1.8 中对集合的底层结构做了调整。 如HashMap从1.7的数据+链表的形式调整为数据+链表+红黑树。 ConcurrentHashMap从分段机制+数组+链表+红黑树到CAS+数组+链表+红黑树。 这里先简要记录,后续会详解Map的原理与...
二、JDK1.8中原理和实现 54 1、ConcurrentHashMap的数据结构 54 2、ConcurrentHashMap的初始化 55 3、Node链表和红黑树结构转换 56 4、ConcurrentHashMap的操作 57 三、JDK1.8实现与1.7相比的重大变化 59 四、 更多...
在jdk1.8中对hashMap等map集合的数据结构优化。hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode ...
在jdk1.8中对hashMap等map集合的数据结构优化。hashMap数据结构的优化 原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode...
2.HashMap在JDK1.7和JDK1.8中有哪些不同?HashMap的底层实现? 3.HashMap的put方法的具体流程? 4.HashMap的扩容操作是怎么实现的? 5.HashMap是怎么解决哈希冲突的? 6.什么是哈希? 7.什么是哈希冲突? 8.HashMap...
存储结构在jdk1.7当中是数组加链表的结构,在jdk1.8当中改为了数组加链表加红黑树的结构。 HashMap在多线程的环境下是不安全的,没有进行加锁措施,所以执行效率快。如果我么需要有一个线程安全的HashMap,可以使用...
在jdk1.8中对hashMap等map集合的数据结构优化。hashMap数据结构的优化,原来的hashMap采用的数据结构是哈希表(数组+链表),hashMap默认大小是16,一个0-15索引的数组,如何往里面存储元素,首先调用元素的hashcode...
jdk1.7 到 jdk1.8 Map 发生了什么变化(底层)? 1.8 之后 hashMap 的数据结构发生了变化,从之前的单纯的数组+链表结构变成数组+链 表+红黑树。也就是说在 JVM 存储 hashMap 的 K-V 时仅仅通过 key 来决定每一个 entry...
众所周知HashMap底层是基于数组+链表组成的,不过在jdk1.7和1.8中具体实现稍有不同。1.7中的数据结构图:先来看看1.7中的实现。这是HashMap中比较核心的几个成员变量;看看分别是什么意思?初始化桶大小,因为底层是...
众所周知 HashMap 底层是基于 数组 + 链表 组成的,不过在 jdk1.7 和 1.8 中具体实现稍有不同。 Base 1.7 1.7 中的数据结构图: 先来看看 1.7 中的实现。 这是 HashMap 中比较核心的几个成员变量;看看分别是...
从jdk1.7 之前 和hashMap的数据结构 和链表的插入方式 死链 谈到 jdk1.8的数据结构 和链表的改进,扩容方式 和触发扩容的条件。 4、为什么使用ConcurrentHashMap? 因为前面提了hashmap是线程不安全的容器,如果要...
│ 高并发编程第一阶段07讲、策略模式在Thread和Runnable中的应用分析.mp4 │ 高并发编程第一阶段08讲、构造Thread对象你也许不知道的几件事.mp4 │ 高并发编程第一阶段09讲、多线程与JVM内存结构的关系,虚拟机...
│ 高并发编程第一阶段07讲、策略模式在Thread和Runnable中的应用分析.mp4 │ 高并发编程第一阶段08讲、构造Thread对象你也许不知道的几件事.mp4 │ 高并发编程第一阶段09讲、多线程与JVM内存结构的关系,虚拟机...
25 3:ServicorTo 和 ServicorFrom 互换................................................................................................................25 2.3.3.1. 2.4.1. 如何确定垃圾 ......................