ConcurrentHashMap--原理

原文网址：ConcurrentHashMap--原理\_IT博客-CSDN博客其他网址辉的博客-CSDN博客ConcurrentHashMap源码分析（JDK8版）\_我什么都希望-CSDN博客Hashmap1.7和1.8区别+ConcurrentHashmap1.7和1.8的区别_hellodake的博客-CSDN博客介绍JDK7和JDK8的区别>

Item

p>JDK1.7

JDK1.8

机制

ReentrantLock+Segment+HashEntry（数组加链表）

synchronized+CAS+HashEntry（数组加链表）+红黑树

读操作：volatile；写操作：synchronized+CAS/td>

Granularity

锁定需要数据操作的Segment

锁定每个桶（数组项）

JDK7在JDK1.7中，ConcurrentHashMap采用ReentrantLock+Segment+HashEntry（数组加链表）的方式来实现，ConcurrentHashMap中的段锁称为Segment，类似于HashMap的结构，即内部有一个Entry数组，并且数组中的每一项第一个元素同时是一个链表和一个ReentrantLock（Segment继承ReentrantLock）。ConcurrentHashMap使用段锁技术将数据分成段存储，然后为每个段数据分配一个锁。当一个线程占用锁访问一段数据时，其他段的数据也可以被其他线程访问。实现真正的并发访问。ConcurrentHashMapput流程内部结构图第一次对key进行hash，通过hash值确定Segment的位置在Segment中进行操作，获取锁并获取当前Segment的HashEntry数组，然后进行第二次对key进行hash，通过hash值确定Segment中位置HashEntry数组的索引位置（头），通过继承ReentrantLock的tryLock方法尝试获取锁。如果获取成功，则直接插入相应位置。如果一个线程已经获取到Segment的锁，则当前线程会自旋继续调用tryLock方法获取锁，指定次数后挂起，等待唤醒然后遍历HashEntry链当前索引，如果有重复键，则替换；如果没有重复键，则将其插入链头释放锁get操作与put操作类似，同样需要两次哈希。但是get操作的concurrenthashmap不需要加锁，因为存储元素都标记为volatile。size操作size操作就是遍历两次所有的Segment，记录每次Segment的modCount值，然后比较两次的modCount。如果相同，则说明该期间没有发生写操作，返回原来遍历的结果。如果判断两次统计的modCount不一致，则必须锁住所有segment，获取并统计count。这期间，每个段都被锁定，不能进行其他操作，计算出来的count自然是准确的。这种结构的优缺点优点写操作时，只能锁定元素所在的Segment，不会影响其他Segment。缺点Hash的过程比普通的HashMap长。JDK8概述JDK8中ConcurrentHashMap的结构与HashMap基本相同。读操作使用CAS，写操作使用synchronized。在JDK8中，Segment被彻底抛弃，取而代之的是Node，其设计思想不再是JDK1.7中的segmentlock思想。节点：一种数据结构，保存了key的key，value，以及key的hash值。其中value和next都用volatile修饰，保证并发的可见性。classNodeimplementsMap.Entry{finalinthash;finalKkey;volatileVval;volatileNodenext;//...省略部分代码}中JDK8ConcurrentHashMap的结构，由于引入了红黑树，使得ConcurrentHashMap的实现非常复杂。我们都知道红黑树是一种性能非常好的二叉搜索树，其搜索性能为O(logN)，但是其实现过程也非常复杂，可读性也很差。DougLea的思维能力确实不是常人可以比的。早期完全采用链表结构时，Map的查找时间复杂度为O(N)。在JDK8中，链表中ConcurrentHashMap的长度大于一定的阈值（8）会将链表转为红黑树，进一步提高其查找性能。ConcurrentHashMap的size方法是如何确定数组的大小的？JDK8初始化put使用CAS操作，...。当一个线程访问哈希表的bucket时，使用sychronized关键字来防止多个线程同时操作同一个bucket（即锁定bucket）。如果该节点的哈希值不小于0，则遍历链表更新该节点或插入新节点；如果节点是TreeBin类型的节点，说明是红黑树结构，则通过putTreeVal方法将该节点插入到红黑树中；节点数更新了，还要考虑扩容和链表转红黑树的问题。finalVputVal(Kkey,Vvalue,booleanonlyIfAbsent){if(key==null||value==null)thrownewNullPointerException();inthash=spread(key.hashCode());for(Node[]tab=table;;){Nodef;诠释n,我,fh;if(tab==null||(n=tab.length)==0)elseif((f=tabAt(tab,i=(n-1)&hash))==null){if(casTabAt(tab,i,null,newNode(hash,key,value,null)))中断；//添加到空bin时没有锁定elseif((fh=f.hash)==MOVED)tab=helpTransfer(tab,f);if(binCount>=TREEIFY_THRESHOLD)getget操作可以是无锁（nolock）是因为Node元素的val指针和next指针被volatile修饰了。在多线程环境下，当线程A修改节点的val或者增加一个新的节点时，对线程B是可见的。size