ConcurrentHashMap#概述

数据结构

jdk1.7

https://tva1.sinaimg.cn/large/00831rSTly1gct5k9ijijj30rh0hbgn1.jpg

jdk1.8

网图https://images.morethink.cn/b3e3671b2edf38a675b5a28587f37ae4.png

如果头节点是Node类型，其后就是一个普通的链表；如果头节点是TreeNode类型，它的后面就是一颗红黑树，TreeNode是Node的子类。链表和红黑树之间可以相互转换：初始的时候是链表，当链表中的元素超过某个阈值时，把链表转换成红黑树；反之，当红黑树中的元素个数小于某个阈值时，再转换为链表。

历史版本对比

从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树。代码量从原来的1000多行变成了 6000多 行，实现上也和原来的分段式存储有很大的区别。

1.数据结构

取消了Segment分段锁的数据结构，取而代之的是数组+链表+红黑树的结构。使用红黑树，当一个槽里有很多元素时，查询时间复杂度从原来的遍历链表O(n)，变成遍历红黑树O(logN)，Hash冲突的问题也会得到较好的解决

2.锁的粒度：

JDK1.7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。原来是对需要进行数据操作的Segment加锁，现调整为对每个头节点分别加锁，其并发度，就是Node数组的长度，初始长度为16，这降低了锁的粒度。

3.并发的扩容：

在JDK 7中，一旦Segment的个数在初始化的时候确立，不能再更改，并发度被固定。之后只是在每个Segment内部扩容，这意味着每个Segment独立扩容，互不影响，不存在并发扩容的问题。但在JDK 8中，相当于只有1个Segment，当一个线程要扩容Node数组的时候，其他线程还要读写，因此处理过会更复杂。

4.代码实现上的区别：

sizeCtl：

多个线程的共享变量，是操作的控制标识符，它的作用不仅包括threshold的作用，在不同的地方有不同的值也有不同的用途。

• -1代表正在初始化
• -N 表示正在进行扩容操作。此时sizeCtl的高16位代表的是当前的容量(并不是数值等于容量大小) 低16位代表线程数 容量16的话计算rs = 32795 也就是 1000 0000 0001 1011 可以看出不同的容量对应不同rs值， rs << 16 的值为 11111111111111111111111111111111 10000000000110110000000000000000, 0-15位用于统计参与扩容的线程数， 16-31位用于代表扩容时容器的大小。
• 正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。

MOVED,TREEBIN,RESERVED ：

MOVED,TREEBIN,RESERVED是用来表示特殊节点的哈希值。该类特殊节点均不含实际元素，且其哈希值被设置为负数和普通节点区分。

//    ForwardingNode标记节点的hash值（表示正在扩容）