java深入学习ConcurrentHashmap (JDK8)
程序员文章站
2022-07-15 13:56:01
...
原博文：http://blog.csdn.net/u010723709/article/details/48007881
看了一些博文，总结下（JDK8源码）：
1、ConcurrentHashmap 使用的是位桶+链表/红黑树实现，结构与hashmap一样，它摒弃了以前Segment（锁段）的概念，而用了一种新的方式实现,CAS算法实现，并且为了实现并发，加入了如treeBin等辅助类；treeBin并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象
2、Node节点类中与hashmap不一样的是，在对value和next属性设置了volatile同步锁，不允许调用setValue方法直接改变Node的value域，但增加了find方法。
3、一个重要的属性sizeCtrl用来表示扩容的情况的标识，正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小；-1代表正在初始化；-N 表示有N-1个线程正在进行扩容操作。
4、put操作
第一步：初始化，对于ConcurrentHashMap来说，调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候。
第二步：在存入值前，key值hash化，遍历位桶数组，如果发现需要扩容，则首先扩容。构建一个2倍中间的nexttable表，在需要复制的地方，先将一个null节点设置为ForwardingNode，然后加锁，复制内容；其他线程遍历到这个节点时，就会跳过往下一个节点继续遍历，直到复制玩内容，sizeCtrl变成扩容后的0.75n
第三步：如果当前hash没被占用，会被直接存储。如果hash有冲突，若当前节点下为链表，则会依次比对，hash和key都相同，则替换value值；没有就将当前值插入到链表最后，当发现链表长多超过8时，会转成红黑树，但在位桶中存的是TreeBin，TreeBin存放的是TreeNode。如果有冲突且节点下为treeBin时，则按照红黑树查找，存放到相应位置。
5、get操作，get方法比较简单，给定一个key来确定value的时候，必须满足两个条件 key相同 hash值相同，对于节点可能在链表或树上的情况，需要分别去查找。
6、size对于ConcurrentHashMap来说，这个table里到底装了多少东西其实是个不确定的数量，因为不可能在调用size()方法的时候像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值，主要运用了mappingCount
看了一些博文，总结下（JDK8源码）：
1、ConcurrentHashmap 使用的是位桶+链表/红黑树实现，结构与hashmap一样，它摒弃了以前Segment（锁段）的概念，而用了一种新的方式实现,CAS算法实现，并且为了实现并发，加入了如treeBin等辅助类；treeBin并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象
2、Node节点类中与hashmap不一样的是，在对value和next属性设置了volatile同步锁，不允许调用setValue方法直接改变Node的value域，但增加了find方法。
3、一个重要的属性sizeCtrl用来表示扩容的情况的标识，正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小；-1代表正在初始化；-N 表示有N-1个线程正在进行扩容操作。
4、put操作
第一步：初始化，对于ConcurrentHashMap来说，调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候。
第二步：在存入值前，key值hash化，遍历位桶数组，如果发现需要扩容，则首先扩容。构建一个2倍中间的nexttable表，在需要复制的地方，先将一个null节点设置为ForwardingNode，然后加锁，复制内容；其他线程遍历到这个节点时，就会跳过往下一个节点继续遍历，直到复制玩内容，sizeCtrl变成扩容后的0.75n
第三步：如果当前hash没被占用，会被直接存储。如果hash有冲突，若当前节点下为链表，则会依次比对，hash和key都相同，则替换value值；没有就将当前值插入到链表最后，当发现链表长多超过8时，会转成红黑树，但在位桶中存的是TreeBin，TreeBin存放的是TreeNode。如果有冲突且节点下为treeBin时，则按照红黑树查找，存放到相应位置。
5、get操作，get方法比较简单，给定一个key来确定value的时候，必须满足两个条件 key相同 hash值相同，对于节点可能在链表或树上的情况，需要分别去查找。
6、size对于ConcurrentHashMap来说，这个table里到底装了多少东西其实是个不确定的数量，因为不可能在调用size()方法的时候像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值，主要运用了mappingCount