ConcurrentHashMap

我们说ConcurrentHashMap是用在多并发场景下的HashMap

 

 JDK1.7

ConcurrentHashMap是由多个HashMap组成，一个HashMap(一个HashMap对应一个元素是链表的数组)对应一个Segment数组中的元素，所以Segment数组中有多少个元素，就代表这个ConcurrentHashMap由多少个HashMap组成，Segment数组长度默认是16，表示ConcurrentHashMap默认支持16个线程并发访问

分段锁：每一把锁只锁Segment数组中的一个Segment，而且这把锁是ReentrantLock可重入锁

 这个部分其实就是HashMap，所以相对于HashMap，ConcurrentHashMap就是多了一个segment数组，segment数组中的每个元素对应一个HashMap

put一条key-value进ConcurrentHashMap的流程：

根据key算出这条key-value应该插入到Segment数组中哪个编号的Segment，然后就跟插入HashMap的流程一样

 JDK1.8的ConcurrentHashMap已经和HashMap的底层数据结构很相似了        

Node数组+链表/红黑树

当数组的长度扩容到64了，而且链表长度达到8之后，再往链表中放元素就会将链表变成红黑树，

链表长度降到6又会退化成链表

对Node数组中的Node结点进行上锁，那对这个结点下面挂的链表或者红黑树进行操作就是线程安全的

如何保证线程安全：CAS+Synchronized

先不上锁，采用cas插入这个key-value，如果插入成功，说明node数组这个位置不存在元素，如果插入失败，说明这个位置已经插入了元素，因此需要用synchronized锁住node数组这个位置的链表头节点，然后进行插入