一、简单回顾ConcurrentHashMap在jdk1.7中的设计
& & 先简单看下ConcurrentHashMap类在jdk1.7中的设计，其基本结构如图所示：
每一个segment都是一个HashEntry&K,V&[] table， table中的每一个元素本质上都是一个HashEntry的单向队列。比如table[3]为首节点，table[3]-&next为节点1，之后为节点2，依次类推。
public class ConcurrentHashMap&K, V& extends AbstractMap&K, V&
implements ConcurrentMap&K, V&, Serializable {
// 将整个hashmap分成几个小的map，每个segment都是一个锁；与hashtable相比，这么设计的目的是对于put, remove等操作，可以减少并发冲突，对
// 不属于同一个片段的节点可以并发操作，大大提高了性能
final Segment&K,V&[]
// 本质上Segment类就是一个小的hashmap，里面table数组存储了各个节点的数据，继承了ReentrantLock, 可以作为互拆锁使用
static final class Segment&K,V& extends ReentrantLock implements Serializable {
transient volatile HashEntry&K,V&[]
transient int
// 基本节点，存储Key， Value值
static final class HashEntry&K,V& {
volatile V
volatile HashEntry&K,V&
二、在jdk1.8中主要做了2方面的改进
改进一：取消segments字段，直接采用transient volatile HashEntry&K,V&[] table保存数据，采用table数组元素作为锁，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。
改进二：将原先table数组＋单向链表的数据结构，变更为table数组＋单向链表＋红黑树的结构。对于hash表来说，最核心的能力在于将key hash之后能均匀的分布在数组中。如果hash之后散列的很均匀，那么table数组中的每个队列长度主要为0或者1。但实际情况并非总是如此理想，虽然ConcurrentHashMap类默认的加载因子为0.75，但是在数据量过大或者运气不佳的情况下，还是会存在一些队列长度过长的情况，如果还是采用单向列表方式，那么查询某个节点的时间复杂度为O(n)；因此，对于个数超过8(默认值)的列表，jdk1.8中采用了红黑树的结构，那么查询的时间复杂度可以降低到O(logN)，可以改进性能。
为了说明以上2个改动，看一下put操作是如何实现的。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node&K,V&[] tab =;) {
Node&K,V& int n, i,
// 如果table为空，初始化；否则，根据hash值计算得到数组索引i，如果tab[i]为空，直接新建节点Node即可。注：tab[i]实质为链表或者红黑树的首节点。
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node&K,V&(hash, key, value, null)))
// no lock when adding to empty bin
// 如果tab[i]不为空并且hash值为MOVED，说明该链表正在进行transfer操作，返回扩容完成后的table。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
V oldVal = null;
// 针对首个节点进行加锁操作，而不是segment，进一步减少线程冲突
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh &= 0) {
binCount = 1;
for (Node&K,V& e =; ++binCount) {
// 如果在链表中找到值为key的节点e，直接设置e.val = value即可。
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.
if (!onlyIfAbsent)
// 如果没有找到值为key的节点，直接新建Node并加入链表即可。
Node&K,V& pred =
if ((e = e.next) == null) {
pred.next = new Node&K,V&(hash, key,
value, null);
// 如果首节点为TreeBin类型，说明为红黑树结构，执行putTreeVal操作。
else if (f instanceof TreeBin) {
binCount = 2;
if ((p = ((TreeBin&K,V&)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.
if (!onlyIfAbsent)
if (binCount != 0) {
// 如果节点数&＝8，那么转换链表结构为红黑树结构。
if (binCount &= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldV
// 计数增加1，有可能触发transfer操作(扩容)。
addCount(1L, binCount);
return null;
另外，在其他方面也有一些小的改进，比如新增字段&transient volatile CounterCell[] counterC 可方便的计算hashmap中所有元素的个数，性能大大优于jdk1.7中的size()方法。
三、ConcurrentHashMap jdk1.7、jdk1.8性能比较
测试程序如下：
public class CompareConcurrentHashMap {
private static ConcurrentHashMap&String, Integer& map = new ConcurrentHashMap&String, Integer&(40000);
public static void putPerformance(int index, int num) {
for (int i = i & (num + index) ; i++)
map.put(String.valueOf(i), i);
public static void getPerformance2() {
long start = System.currentTimeMillis();
for (int i = 0; i & 400000; i++)
map.get(String.valueOf(i));
long end = System.currentTimeMillis();
System.out.println(&get: it costs & + (end - start) + & ms&);
public static void main(String[] args) throws InterruptedException {
long start = System.currentTimeMillis();
final CountDownLatch cdLatch = new CountDownLatch(4);
for (int i = 0; i & 4; i++) {
final int finalI =
new Thread(new Runnable() {
public void run() {
CompareConcurrentHashMap.putPerformance(100000 * finalI, 100000);
cdLatch.countDown();
}).start();
cdLatch.await();
long end = System.currentTimeMillis();
System.out.println(&put: it costs & + (end - start) + & ms&);
CompareConcurrentHashMap.getPerformance2();
程序运行多次后取平均值，结果如下：
四、Collections.synchronizedList和CopyOnWriteArrayList性能分析
CopyOnWriteArrayList在线程对其进行变更操作的时候，会拷贝一个新的数组以存放新的字段，因此写操作性能很差；而Collections.synchronizedList读操作采用了synchronized，因此读性能较差。以下为测试程序：
public class App {
private static List&String& arrayList = Collections.synchronizedList(new ArrayList&String&());
private static List&String& copyOnWriteArrayList = new CopyOnWriteArrayList&String&();
private static CountDownLatch cdl1 = new CountDownLatch(2);
private static CountDownLatch cdl2 = new CountDownLatch(2);
private static CountDownLatch cdl3 = new CountDownLatch(2);
private static CountDownLatch cdl4 = new CountDownLatch(2);
static class Thread1 extends Thread {
public void run() {
for (int i = 0; i & 10000; i++)
arrayList.add(String.valueOf(i));
cdl1.countDown();
static class Thread2 extends Thread {
public void run() {
for (int i = 0; i & 10000; i++)
copyOnWriteArrayList.add(String.valueOf(i));
cdl2.countDown();
static class Thread3 extends Thread1 {
public void run() {
int size = arrayList.size();
for (int i = 0; i & i++)
arrayList.get(i);
cdl3.countDown();
static class Thread4 extends Thread1 {
public void run() {
int size = copyOnWriteArrayList.size();
for (int i = 0; i & i++)
copyOnWriteArrayList.get(i);
cdl4.countDown();
public static void main(String[] args) throws InterruptedException {
long start1 = System.currentTimeMillis();
new Thread1().start();
new Thread1().start();
cdl1.await();
System.out.println(&arrayList add: & + (System.currentTimeMillis() - start1));
long start2 = System.currentTimeMillis();
new Thread2().start();
new Thread2().start();
cdl2.await();
System.out.println(&copyOnWriteArrayList add: & + (System.currentTimeMillis() - start2));
long start3 = System.currentTimeMillis();
new Thread3().start();
new Thread3().start();
cdl3.await();
System.out.println(&arrayList get: & + (System.currentTimeMillis() - start3));
long start4 = System.currentTimeMillis();
new Thread4().start();
new Thread4().start();
cdl4.await();
System.out.println(&copyOnWriteArrayList get: & + (System.currentTimeMillis() - start4));
结果如下：
本文已收录于以下专栏：
相关文章推荐
HashMap分析: http://www.begincode.net/blog/55
先看一段代码
public class Main {
private static Executor...
ConcurrentHashMap的锁分段技术：假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效的提高并发访问效率，...
人生苦短，都说必须python，那么我分享下我是如何从小白成为Python资深开发者的吧。2014年我大学刚毕业..
读完本文你将了解到：
什么是红黑树黑色高度
红黑树的 5 个特性
红黑树的左旋右旋
指定节点 x 的左旋 右图转成左图
指定节点 y 的右旋左图转成右图
红黑树的平衡插入
二叉查找树的插入
插入后调整...
并发环境下为什么使用ConcurrentHashMap
1. HashMap在高并发的环境下，执行put操作会导致HashMap的Entry链表形成环形数据结构，从而导致Entry的next节点始终...
在JDK8中，ConcurrentHashMap实现机制较JDK7发生了很大变化，其摒弃了分段锁（Segment）的概念，而是利用CAS算法，与Hashtable一样，内部由“数组+链表+红黑树”的方...
1.7和1.8中的ConCurrentHashMap对比
jdk1.7中采用Segment + HashEntry的方式进行实现，
ConcurrentHa...
《Java源码分析》：ConcurrentHashMap
JDK1.8最近一直在看关于J.U.C中的源码，了解原子操作，了解锁机制，了解多线程并发等等。但是ConcurrentHashMap一直拖着...
21.HashMap的工作原理是什么?
HashMap内部是通过一个数组实现的，只是这个数组比较特殊，数组里存储的元素是一个Entry实体(jdk 8为Node)，这个Entry实体主要包含key...
转载文章，原博客地址为：http://blog.csdn.net/u/article/details/
jdk1.8和jdk1.7对于ConcurrentHashM...
今天看到一篇博客：jdk1.8的HashMap和ConcurrentHashMap，我想起了前段时间面试的一个问题：ConcurrentHashMap(JDK1.8)为什么要使用synchronize...
他的最新文章
讲师：董西成
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)博客分类：
1.前言。
&& 本地缓存和复杂的单例写起来不仅效率低下，而且费时。ConcurrentHashMap+computeIfAbsent使得可以直接快速构建。
2.例子.
&
import java.util.HashM
import java.util.HashS
import java.util.M
import java.util.concurrent.ConcurrentHashM
import java.util.concurrent.ExecutorS
import java.util.concurrent.E
import java.util.concurrent.TimeU
public class Main {
static Map&Integer, Integer& cache = new ConcurrentHashMap&&();
public static void main(String[] args) throws InterruptedException {
cache.put(0, 0);
cache.put(1, 1);
// 普通方式
System.out.println("Fibonacci(7) = " + fibonacci(7));
// 采用java7的同步线程方式及java8的本地缓存的方式
System.out.println("FibonacciJava8(7) = " + fibonacciJava8(7));
System.out.println("FibonacciJava7(7) = " + fibonacciJava7(7));
// 构建多值Map样例代码
Map&String, HashSet&String&& map1 = new HashMap&&();
puteIfAbsent("fruits", k -& genValue(k)).add("apple");
puteIfAbsent("fruits", k -& genValue(k)).add("orange");
puteIfAbsent("fruits", k -& genValue(k)).add("pear");
puteIfAbsent("fruits", k -& genValue(k)).add("banana");
puteIfAbsent("fruits", k -& genValue(k)).add("water");
System.out.println(map1);
//测试多线程并发处理，是否同步操作
Map&String, String& map2 = new ConcurrentHashMap&&();
ExecutorService exec = Executors.newCachedThreadPool();
for (int i = 0; i & 5; i++) {
exec.execute(() -& {
puteIfAbsent("name", k -& genValue2(k));
puteIfAbsent("addr", k -& genValue2(k));
puteIfAbsent("email", k -& genValue2(k));
puteIfAbsent("mobile", k -& genValue2(k));
exec.shutdown();
exec.awaitTermination(1, TimeUnit.SECONDS);
System.out.println(map2);
static HashSet&String& genValue(String str) {
return new HashSet&String&();
static String genValue2(String str) {
System.out.println("===");
return str + "2";
* 普通的实现方式 普通方式使用大量的计算，存在性能问题. 并且计算量随着n的增加呈指数级增加，需要用到一些缓存策略，并且是线程安全的.
* @param n
static int fibonacci(int n) {
if (n == 0 || n == 1)
System.out.println("calculating Fibonacci(" + n + ")");
return fibonacci(n - 2) + fibonacci(n - 1);
* 采用java8的本地缓存方式 如果缓存MAP中不存在指定key的值，会自动调用mappingFunction(key)计算key的value
* 然后将key = value放入到缓存Map,java8会使用thread-safe的方式从cache中存取记录
* @param n
static int fibonacciJava8(int n) {
puteIfAbsent(n, (key) -& {
System.out.println("calculating FibonacciJava8 " + n);
return fibonacciJava8(n - 2) + fibonacciJava8(n - 1);
* 在java7中的实现方式
* 在java7中，通过synchronized进行线程同步，检查缓存是否存在key对应的值，如果不存在才进行计算并放入缓存中
* 为了更好的性能，需要使用 double-checked locking，那样代码会更复杂
* @param n
static int fibonacciJava7(int n) {
if (n == 0 || n == 1)
Integer result = cache.get(n);
if (result == null) {
synchronized (cache) {
result = cache.get(n);
if (result == null) {
System.out.println("calculating FibonacciJava7(" + n + ")");
result = fibonacciJava7(n - 2) + fibonacciJava7(n - 1);
cache.put(n, result);
& 运行结果:
&
calculating Fibonacci(7)
calculating Fibonacci(5)
calculating Fibonacci(3)
calculating Fibonacci(2)
calculating Fibonacci(4)
calculating Fibonacci(2)
calculating Fibonacci(3)
calculating Fibonacci(2)
calculating Fibonacci(6)
calculating Fibonacci(4)
calculating Fibonacci(2)
calculating Fibonacci(3)
calculating Fibonacci(2)
calculating Fibonacci(5)
calculating Fibonacci(3)
calculating Fibonacci(2)
calculating Fibonacci(4)
calculating Fibonacci(2)
calculating Fibonacci(3)
calculating Fibonacci(2)
Fibonacci(7) = 13
calculating FibonacciJava8 7
calculating FibonacciJava8 5
calculating FibonacciJava8 3
calculating FibonacciJava8 2
calculating FibonacciJava8 4
calculating FibonacciJava8 6
FibonacciJava8(7) = 13
FibonacciJava7(7) = 13
{fruits=[orange, banana, apple, pear, water]}
{name=name2, mobile=mobile2, addr=addr2, email=email2}
浏览: 1010200 次
来自: 深圳
&div class=&quote_title ...
另外内存泄漏一般也不是指计算时溢出。而是指某些对象已经不再使用 ...
Long.MAX_VALUE应该是(2^63)-1，而不是64 ...
java-lxm 写道好湿好湿好湿谢谢: )。
好湿好湿好湿博客分类：
ConcurrentHashMap是线程安全的概念已经深入人心，让我们在使用的时候有些大意了，我也懒得动脑子，直接使用，结果碰到钉子了.
这个问题让我很郁闷，程序逻辑全是对的，但是问题却明明摆在那边，最后怀疑是HashMap的问题。
package com.taobao.mmp.
import java.util.HashM
import java.util.M
import java.util.concurrent.ConcurrentHashM
import com.taobao.mmp.dataobject.ServiceDO;
public class TTTT {
private static Map&Long, ServiceDO& widgetCacheMap = new ConcurrentHashMap&Long, ServiceDO&();
* @param args
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int i=0;i&10000;i++){
Thread tt = new Thread(new Rund());
tt.start();
static class Rund implements Runnable{
public void run() {
// TODO Auto-generated method stub
* 1W次，总有那么几次线程不安全
public void test(){
TTTT tt = new TTTT();
int s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
public void set() {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
mm.put(1L, ss);
widgetCacheMap =
public void change(){
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
mm.put(1L, ss);
widgetCacheMap =
执行10000次，多执行几次，或许你会发现，真的一般情况下是线程安全的，但是在大量并发的时候，线程就变得不那么安全了.
输出结果如下:
为什么出现这种情况，我在第一个地方设置值，然后取值，第二个地方再设置值，然后取值，两个值应该不同的，判断相同的时候，既然出现了。有人怀疑是ConcurrentHashMap,那你可以换成HashMap试试.结果一样.
为什么是2,2不是1,1；当然一般情况下是1:2，并发情况下就变成2,2了.
有人怀疑是初始化widgetCacheMap的问题，那么改代码如下:
public void set() {
//Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
widgetCacheMap.put(1L, ss);
//widgetCacheMap =
public void change(){
//Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
widgetCacheMap.put(1L, ss);
//widgetCacheMap =
真是不改不知道，一改吓一跳，这回出现刚才说的情况1,1
而且改了之后其并发问题更严重了，因为这里每一次put都需要加行锁，其并发的概念也就上升了.
推荐写法还是按第一次方法，对象的覆盖是原子的，最好加一把锁，否则你第一次覆盖了，第二次又被别人覆盖了.
于是代码如下:
public void set() {
synchronized (widgetCacheMap) {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(1);
mm.put(1L, ss);
widgetCacheMap =
public void change(){
synchronized (widgetCacheMap) {
Map mm= new HashMap();
ServiceDO ss = new ServiceDO();
ss.setStatus(2);
mm.put(1L, ss);
widgetCacheMap =
保持widgetCacheMap的变更成原子状态。当然还会出现上面的情况，这是为什么呢。
因为每一个线程获取的时候，可能取的是原子1,也可能是原子2,如果在多线程获取的时候加一把锁，那么获取的就是原子X,但至少是一个原子，要么1,要么2.
于是代码如下:
public void test(){
synchronized (widgetCacheMap) {
TTTT tt = new TTTT();
int s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
结果又出现如上现象，这是为什么呢，因为锁里面还加着锁，锁最好是原子化，尽量保持最小范围，不能价懒，像我一样就悲剧了.
* 1W次，总有那么几次线程不安全
public void test(){
TTTT tt = new TTTT();
int s1 = -1;
synchronized (widgetCacheMap) {
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
synchronized (widgetCacheMap) {
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
还是出现上面这种情况，通阅全码，发现每一次都是原子了，应该没问题了。
但是还需要考虑run方法是多线程的，只有一个线程进入test，那就算原子了.如下:
唉，这是为什么呢，syn不起作用？
开始怀疑，于是去掉所有的syn，只添加run方法中的如下:
* 1W次，总有那么几次线程不安全
void test(){
synchronized (widgetCacheMap) {
TTTT tt = new TTTT();
int s1 = -1;
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
整个进行原子操作，结果让人晕死。还是出现在，最后想了想，原来Hash或者CurrentHashMap也一样，在中间change了一下，而syn锁定的是一个不变的东西。
于如改代码如下:
* 1W次，总有那么几次线程不安全
void test(){
synchronized ("") {
TTTT tt = new TTTT();
int s1 = -1;
s1 = widgetCacheMap.get(1L).getStatus();
tt.change();
int s2 = -2;
s2 = widgetCacheMap.get(1L).getStatus();
if(s1==s2){
System.out.println(s1+":"+s2);
这回你怎么执行都是原子操作了。
总结：ConcurrentHashMap是线程安全的，那是在他们的内部操作，其外部操作还是需要自己来保证其同步的，特别是静态的ConcurrentHashMap,其有更新和查询的过程，要保证其线程安全，需要syn一个不可变的参数才能保证其原子性
浏览 19038
论坛回复 /
(12 / 3712)
今天无意中看到你这篇博客，我觉得有问题：&&& 1.widgetCacheMap = mm你这样一来，widgetCacheMap指向了一个HashMap,它已经不是一个ConcurrentHashMap了；&&& 2.ConcurrentHashMap本身确实是一个线程安全的数据结构，但它的线程安全是有条件的，你的这个test方法：&&& public void test(){& &&&&&&&&&&&&&&& TTTT tt = new TTTT();& &&&&&&&&&&&&&&& tt.set();& &&&&&&&&&&&&&&& int s1 = widgetCacheMap.get(1L).getStatus();& &&&&&&&&&&&&&&& tt.change();& &&&&&&&&&&&&&&& int s2 = widgetCacheMap.get(1L).getStatus();& &&&&&&&&&&&&&&& if(s1==s2){& &&&&&&&&&&&&&&&&&&& System.out.println(s1+":"+s2);& &&&&&&&&&&&&&&& }& &&&&&&& } 本身是有问题的，假如某一个线程刚执行完tt.set()中的 widgetCacheMap.put(1L,ss);然后另个线程立刻开始执行tt.change()中的 widgetCacheMap.put(1L,ss);并且执行完毕，那么第一个数就变成了2，同理第二个数也可能变成1.这个测试用例是有问题的，有事务的意途，但没有事务的约束，你测的不是ConcurrentHashMap，而是两个set和change的事务性保证
这个内部put和get是原子的，就是说肯定不会出现内部数据结构错误吧。至于put和get的对象，这个状态的变化的同步可能还是需要我们自己来做。是的
浏览: 298577 次
来自: 杭州
public static final Logger log ...
java程序语言学习教程 地址http://www.zuida ...
[img][/img]ConcurrentHashMap原理分析（1.7与1.8）
我的图书馆
ConcurrentHashMap原理分析（1.7与1.8）
以前写过介绍HashMap的文章，文中提到过HashMap在put的时候，插入的元素超过了容量（由负载因子决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进行put操作，如果hash值相同，可能出现同时在同一数组下用链表表示，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。
我们来了解另一个键值存储集合HashTable，它是线程安全的，它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争一把锁，在多线程的环境下，它是安全的，但是无疑是效率低下的。
其实HashTable有很多的优化空间，锁住整个table这么粗暴的方法可以变相的柔和点，比如在多线程的环境下，对不同的数据集进行操作时其实根本就不需要去竞争一个锁，因为他们不同hash值，不会因为rehash造成线程不安全，所以互不影响，这就是锁分离技术，将锁的粒度降低，利用多个锁来控制多个小的table，这就是这篇文章的主角ConcurrentHashMap JDK1.7版本的核心思想
ConcurrentHashMap
JDK1.7的实现
在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：
Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，也就是上面的提到的锁分离技术，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样
ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的大小，用ssize来表示，如下所示
123456int sshift = 0;int ssize = 1;while (ssize & concurrencyLevel) {&&&&++&&&&ssize &&= 1;}
如上所示，因为ssize用位于运算来计算（ssize &&=1），所以Segment的大小取值都是以2的N次方，无关concurrencyLevel的取值，当然concurrencyLevel最大只能用16位的二进制来表示，即65536，换句话说，Segment的大小最多65536个，没有指定concurrencyLevel元素初始化，Segment的大小ssize默认为16
每一个Segment元素下的HashEntry的初始化也是按照位于运算来计算，用cap来表示，如下所示
123int cap = 1;while (cap & c)&&&&cap &&= 1;
如上所示，HashEntry大小的计算也是2的N次方（cap &&=1）， cap的初始值为1，所以HashEntry最小的容量为2
对于ConcurrentHashMap的数据插入，这里要进行两次Hash去定位数据的存储位置
1static class Segment&K,V& extends ReentrantLock implements Serializable {
从上Segment的继承体系可以看出，Segment实现了ReentrantLock,也就带有锁的功能，当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒
ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null
计算ConcurrentHashMap的元素大小是一个有趣的问题，因为他是并发操作的，就是在你计算size的时候，他还在并发的插入数据，可能会导致你计算出来的size和你实际的size有相差（在你return size的时候，插入了多个数据），要解决这个问题，JDK1.7版本用两种方案
123456789101112131415161718192021try {&&&&for (;;) {&&&&&&&&if (retries++ == RETRIES_BEFORE_LOCK) {&&&&&&&&&&&&for (int j = 0; j & segments. ++j) ensureSegment(j).lock(); // force creation&&&&&&&&}&&&&&&&&sum = 0L;&&&&&&&&size = 0;&&&&&&&&overflow = false;&&&&&&&&for (int j = 0; j & segments. ++j) {&&&&&&&&&&&&Segment&K,V& seg = segmentAt(segments, j);&&&&&&&&&&&&if (seg != null) { sum += seg.modC int c = seg. if (c & 0 || (size += c) & 0)&&&&&&&&&&&&&&&overflow = true;&&&&&&&&&&&&} }&&&&&&&&if (sum == last) break;&&&&&&&&last = } }finally {&&&&if (retries & RETRIES_BEFORE_LOCK) {&&&&&&&&for (int j = 0; j & segments. ++j)&&&&&&&&&&&&segmentAt(segments, j).unlock();&&&&}}
第一种方案他会使用不加锁的模式去尝试多次计算ConcurrentHashMap的size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的
第二种方案是如果第一种方案不符合，他就会给每个Segment加上锁，然后计算ConcurrentHashMap的size返回
JDK1.8的实现
JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本
在深入JDK1.8的put和get实现之前要知道一些常量设计和数据结构，这些是构成ConcurrentHashMap实现结构的基础，下面看一下基本属性：
123456789101112131415161718192021222324252627282930313233343536// node数组最大容量：2^30=private static final int MAXIMUM_CAPACITY = 1 && 30;// 默认初始值，必须是2的幕数private static final int DEFAULT_CAPACITY = 16;//数组可能最大值，需要与toArray（）相关方法关联static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//并发级别，遗留下来的，为兼容以前的版本private static final int DEFAULT_CONCURRENCY_LEVEL = 16;// 负载因子private static final float LOAD_FACTOR = 0.75f;// 链表转红黑树阀值,& 8 链表转换为红黑树static final int TREEIFY_THRESHOLD = 8;//树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，&=UNTREEIFY_THRESHOLD 则untreeify(lo)）static final int UNTREEIFY_THRESHOLD = 6;static final int MIN_TREEIFY_CAPACITY = 64;private static final int MIN_TRANSFER_STRIDE = 16;private static int RESIZE_STAMP_BITS = 16;// 2^15-1，help resize的最大线程数private static final int MAX_RESIZERS = (1 && (32 - RESIZE_STAMP_BITS)) - 1;// 32-16=16，sizeCtl中记录size大小的偏移量private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;// forwarding nodes的hash值static final int MOVED&&&& = -1; // 树根节点的hash值static final int TREEBIN&& = -2; // ReservationNode的hash值static final int RESERVED& = -3; // 可用处理器数量static final int NCPU = Runtime.getRuntime().availableProcessors();//存放node的数组transient volatile Node&K,V&[]/*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义&*当为负数时：-1代表正在初始化，-N代表有N-1个线程正在 进行扩容&*当为0时：代表当时的table还没有被初始化&*当为正数时：表示初始化或者下一次进行扩容的大小private transient volatile int sizeC
基本属性定义了ConcurrentHashMap的一些边界以及操作时的一些控制，下面看一些内部的一些结构组成，这些是整个ConcurrentHashMap整个数据结构的核心
Node是ConcurrentHashMap存储结构的基本单元，继承于HashMap中的Entry，用于存储数据，源代码如下
12345678910111213141516171819202122232425262728293031323334353637383940414243static class Node&K,V& implements Map.Entry&K,V& {&&&&//链表的数据结构&&&&final int &&&&final K&&&&//val和next都会在扩容时发生变化，所以加上volatile来保持可见性和禁止重排序&&&&volatile V&&&&volatile Node&K,V&&&&&Node(int hash, K key, V val, Node&K,V& next) {&&&&&&&&this.hash =&&&&&&&&this.key =&&&&&&&&this.val =&&&&&&&&this.next =&&&&}&&&&public final K getKey()&&&&&& { return
}&&&&public final V getValue()&&&& { return
}&&&&public final int hashCode()&& { return key.hashCode() ^ val.hashCode(); }&&&&public final String toString(){ return key + "=" + }&&&&//不允许更新value& &&&&public final V setValue(V value) {&&&&&&&&throw new UnsupportedOperationException();&&&&}&&&&public final boolean equals(Object o) {&&&&&&&&Object k, v, Map.Entry&?,?&&&&&&&&&return ((o instanceof Map.Entry) &&&&&&&&&&&&&&&&&&(k = (e = (Map.Entry&?,?&)o).getKey()) != null &&&&&&&&&&&&&&&&&&(v = e.getValue()) != null &&&&&&&&&&&&&&&&&&(k == key || k.equals(key)) &&&&&&&&&&&&&&&&&&(v == (u = val) || v.equals(u)));&&&&}&&&&//用于map中的get（）方法，子类重写&&&&Node&K,V& find(int h, Object k) {&&&&&&&&Node&K,V& e = this;&&&&&&&&if (k != null) {&&&&&&&&&&&&do {&&&&&&&&&&&&&&&&K&&&&&&&&&&&&&&&&if (e.hash == h &&&&&&&&&&&&&&&&&&&&&&((ek = e.key) == k || (ek != null && k.equals(ek))))&&&&&&&&&&&&&&&&&&&&return e;&&&&&&&&&&&&} while ((e = e.next) != null);&&&&&&&&}&&&&&&&&return null;&&&&}}
Node数据结构很简单，从上可知，就是一个链表，但是只允许对数据进行查找，不允许进行修改
TreeNode继承与Node，但是数据结构换成了二叉树结构，它是红黑树的数据的存储结构，用于红黑树中存储数据，当链表的节点数大于8时会转换成红黑树的结构，他就是通过TreeNode作为存储结构代替Node来转换成黑红树源代码如下
123456789101112131415161718192021222324252627282930313233343536373839404142434445static final class TreeNode&K,V& extends Node&K,V& {&&&&//树形结构的属性定义&&&&TreeNode&K,V&& // red-black tree links&&&&TreeNode&K,V&&&&&TreeNode&K,V&&&&&TreeNode&K,V&&&& // needed to unlink next upon deletion&&&&boolean
//标志红黑树的红节点&&&&TreeNode(int hash, K key, V val, Node&K,V& next,&&&&&&&&&&&&&TreeNode&K,V& parent) {&&&&&&&&super(hash, key, val, next);&&&&&&&&this.parent =&&&&}&&&&Node&K,V& find(int h, Object k) {&&&&&&&&return findTreeNode(h, k, null);&&&&}&&&&//根据key查找 从根节点开始找出相应的TreeNode，&&&&final TreeNode&K,V& findTreeNode(int h, Object k, Class&?& kc) {&&&&&&&&if (k != null) {&&&&&&&&&&&&TreeNode&K,V& p = this;&&&&&&&&&&&&do& {&&&&&&&&&&&&&&&&int ph, K TreeNode&K,V&&&&&&&&&&&&&&&&&TreeNode&K,V& pl = p.left, pr = p.&&&&&&&&&&&&&&&&if ((ph = p.hash) & h)&&&&&&&&&&&&&&&&&&&&p =&&&&&&&&&&&&&&&&else if (ph & h)&&&&&&&&&&&&&&&&&&&&p =&&&&&&&&&&&&&&&&else if ((pk = p.key) == k || (pk != null && k.equals(pk)))&&&&&&&&&&&&&&&&&&&&return p;&&&&&&&&&&&&&&&&else if (pl == null)&&&&&&&&&&&&&&&&&&&&p =&&&&&&&&&&&&&&&&else if (pr == null)&&&&&&&&&&&&&&&&&&&&p =&&&&&&&&&&&&&&&&else if ((kc != null ||&&&&&&&&&&&&&&&&&&&&&&&&&&(kc = comparableClassFor(k)) != null) &&&&&&&&&&&&&&&&&&&&&&&&&&&(dir = compareComparables(kc, k, pk)) != 0)&&&&&&&&&&&&&&&&&&&&p = (dir & 0) ? pl :&&&&&&&&&&&&&&&&else if ((q = pr.findTreeNode(h, k, kc)) != null)&&&&&&&&&&&&&&&&&&&&return q;&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&p =&&&&&&&&&&&&} while (p != null);&&&&&&&&}&&&&&&&&return null;&&&&}}
TreeBin从字面含义中可以理解为存储树形结构的容器，而树形结构就是指TreeNode，所以TreeBin就是封装TreeNode的容器，它提供转换黑红树的一些条件和锁的控制，部分源码结构如下
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758static final class TreeBin&K,V& extends Node&K,V& {&&&&//指向TreeNode列表和根节点&&&&TreeNode&K,V&&&&&volatile TreeNode&K,V&&&&&volatile T&&&&volatile int lockS&&&&// 读写锁状态&&&&static final int WRITER = 1; // 获取写锁的状态&&&&static final int WAITER = 2; // 等待写锁的状态&&&&static final int READER = 4; // 增加数据时读锁的状态&&&&/**&&&&&* 初始化红黑树&&&&&*/&&&&TreeBin(TreeNode&K,V& b) {&&&&&&&&super(TREEBIN, null, null, null);&&&&&&&&this.first =&&&&&&&&TreeNode&K,V& r = null;&&&&&&&&for (TreeNode&K,V& x = b, x != null; x = next) {&&&&&&&&&&&&next = (TreeNode&K,V&)x.&&&&&&&&&&&&x.left = x.right = null;&&&&&&&&&&&&if (r == null) {&&&&&&&&&&&&&&&&x.parent = null;&&&&&&&&&&&&&&&&x.red = false;&&&&&&&&&&&&&&&&r =&&&&&&&&&&&&}&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&K k = x.&&&&&&&&&&&&&&&&int h = x.&&&&&&&&&&&&&&&&Class&?& kc = null;&&&&&&&&&&&&&&&&for (TreeNode&K,V& p =;) {&&&&&&&&&&&&&&&&&&&&int dir,&&&&&&&&&&&&&&&&&&&&K pk = p.&&&&&&&&&&&&&&&&&&&&if ((ph = p.hash) & h)&&&&&&&&&&&&&&&&&&&&&&&&dir = -1;&&&&&&&&&&&&&&&&&&&&else if (ph & h)&&&&&&&&&&&&&&&&&&&&&&&&dir = 1;&&&&&&&&&&&&&&&&&&&&else if ((kc == null &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(kc = comparableClassFor(k)) == null) ||&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(dir = compareComparables(kc, k, pk)) == 0)&&&&&&&&&&&&&&&&&&&&&&&&dir = tieBreakOrder(k, pk);&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& xp =&&&&&&&&&&&&&&&&&&&&if ((p = (dir &= 0) ? p.left : p.right) == null) {&&&&&&&&&&&&&&&&&&&&&&&&x.parent =&&&&&&&&&&&&&&&&&&&&&&&&if (dir &= 0)&&&&&&&&&&&&&&&&&&&&&&&&&&&&xp.left =&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&xp.right =&&&&&&&&&&&&&&&&&&&&&&&&r = balanceInsertion(r, x);&&&&&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&this.root =&&&&&&&&assert checkInvariants(root);&&&&}&&&&......}
介绍了ConcurrentHashMap主要的属性与内部的数据结构，现在通过一个简单的例子以debug的视角看看ConcurrentHashMap的具体操作细节
123456789101112131415public class TestConcurrentHashMap{&&& &&&&public static void main(String[] args){&&&&&&&&ConcurrentHashMap&String,String& map = new ConcurrentHashMap(); //初始化ConcurrentHashMap&&&&&&&&//新增个人信息&&&&&&&&map.put("id","1");&&&&&&&&map.put("name","andy");&&&&&&&&map.put("sex","男");&&&&&&&&//获取姓名&&&&&&&&String name = map.get("name");&&&&&&&&Assert.assertEquals(name,"andy");&&&&&&&&//计算大小&&&&&&&&int size = map.size();&&&&&&&&Assert.assertEquals(size,3);&&&&}}
我们先通过new ConcurrentHashMap()来进行初始化　　
12public ConcurrentHashMap() {}
由上你会发现ConcurrentHashMap的初始化其实是一个空实现，并没有做任何事，这里后面会讲到，这也是和其他的集合类有区别的地方，初始化操作并不是在构造函数实现的，而是在put操作中实现，当然ConcurrentHashMap还提供了其他的构造函数，有指定容量大小或者指定负载因子，跟HashMap一样，这里就不做介绍了
在上面的例子中我们新增个人信息会调用put方法，我们来看下
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071public 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进行迭代&&&&&&&&Node&K,V& int n, i,&&&&&&&&//这里就是上面构造方法没有进行初始化，在这里进行判断，为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 =; ++binCount) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&K&&&&&&&&&&&&&&&&&&&&&&&&&&&&//这里涉及到相同的key进行put就会覆盖原先的value&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (e.hash == hash &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&((ek = e.key) == key ||&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(ek != null && key.equals(ek)))) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&oldVal = e.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (!onlyIfAbsent)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&e.val =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V& pred =&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((e = e.next) == null) {& //插入链表尾部&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&pred.next = new Node&K,V&(hash, key,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&value, null);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&else if (f instanceof TreeBin) {//红黑树结构&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V&&&&&&&&&&&&&&&&&&&&&&&&&binCount = 2;&&&&&&&&&&&&&&&&&&&&&&&&//红黑树结构旋转插入&&&&&&&&&&&&&&&&&&&&&&&&if ((p = ((TreeBin&K,V&)f).putTreeVal(hash, key,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&value)) != null) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&oldVal = p.&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (!onlyIfAbsent)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&p.val =&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&if (binCount != 0) { //如果链表的长度大于8时就会进行红黑树的转换&&&&&&&&&&&&&&&&if (binCount &= TREEIFY_THRESHOLD)&&&&&&&&&&&&&&&&&&&&treeifyBin(tab, i);&&&&&&&&&&&&&&&&if (oldVal != null)&&&&&&&&&&&&&&&&&&&&return oldV&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&}&&&&}&&&&addCount(1L, binCount);//统计size，并且检查是否需要扩容&&&&return null;}
这个put的过程很清晰，对当前的table进行无条件自循环直到put成功，可以分成以下六步流程来概述
如果没有初始化就先调用initTable（）方法来进行初始化过程
如果没有hash冲突就直接CAS插入
如果还在进行扩容操作就先进行扩容
如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
如果添加成功就调用addCount（）方法统计size，并且检查是否需要扩容
现在我们来对每一步的细节进行源码分析，在第一步中，符合条件会进行初始化操作，我们来看看initTable（）方法
12345678910111213141516171819202122232425/**&* Initializes table, using the size recorded in sizeCtl.&*/private final Node&K,V&[] initTable() {&&&&Node&K,V&[] int &&&&while ((tab = table) == null || tab.length == 0) {//空的table才能进入初始化操作&&&&&&&&if ((sc = sizeCtl) & 0) //sizeCtl&0表示其他线程已经在初始化了或者扩容了，挂起当前线程 &&&&&&&&&&&&Thread.yield(); // lost just spin&&&&&&&&else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {//CAS操作SIZECTL为-1，表示初始化状态&&&&&&&&&&&&try {&&&&&&&&&&&&&&&&if ((tab = table) == null || tab.length == 0) {&&&&&&&&&&&&&&&&&&&&int n = (sc & 0) ? sc : DEFAULT_CAPACITY;&&&&&&&&&&&&&&&&&&&&@SuppressWarnings("unchecked")&&&&&&&&&&&&&&&&&&&&Node&K,V&[] nt = (Node&K,V&[])new Node&?,?&[n];//初始化&&&&&&&&&&&&&&&&&&&&table = tab =&&&&&&&&&&&&&&&&&&&&sc = n - (n &&& 2);//记录下次扩容的大小&&&&&&&&&&&&&&&&}&&&&&&&&&&&&} finally {&&&&&&&&&&&&&&&&sizeCtl =&&&&&&&&&&&&}&&&&&&&&&&&&break;&&&&&&&&}&&&&}&&&&return }
在第二步中没有hash冲突就直接调用Unsafe的方法CAS插入该元素，进入第三步如果容器正在扩容，则会调用helpTransfer（）方法帮助扩容，现在我们跟进helpTransfer（）方法看看
12345678910111213141516171819202122/**&*帮助从旧的table的元素复制到新的table中&*/final Node&K,V&[] helpTransfer(Node&K,V&[] tab, Node&K,V& f) {&&&&Node&K,V&[] nextT int &&&&if (tab != null && (f instanceof ForwardingNode) &&&&&&&&&&(nextTab = ((ForwardingNode&K,V&)f).nextTable) != null) { //新的table nextTba已经存在前提下才能帮助扩容&&&&&&&&int rs = resizeStamp(tab.length);&&&&&&&&while (nextTab == nextTable && table == tab &&&&&&&&&&&&&&&&&(sc = sizeCtl) & 0) {&&&&&&&&&&&&if ((sc &&& RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||&&&&&&&&&&&&&&&&sc == rs + MAX_RESIZERS || transferIndex &= 0)&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {&&&&&&&&&&&&&&&&transfer(tab, nextTab);//调用扩容方法&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&return nextT&&&&}&&&&return }
其实helpTransfer（）方法的目的就是调用多个工作线程一起帮助进行扩容，这样的效率就会更高，而不是只有检查到要扩容的那个线程进行扩容操作，其他线程就要等待扩容操作完成才能工作既然这里涉及到扩容的操作，我们也一起来看看扩容方法transfer（）
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152private final void transfer(Node&K,V&[] tab, Node&K,V&[] nextTab) {&&&&&&&&int n = tab.length,&&&&&&&&// 每核处理的量小于16，则强制赋值16&&&&&&&&if ((stride = (NCPU & 1) ? (n &&& 3) / NCPU : n) & MIN_TRANSFER_STRIDE)&&&&&&&&&&&&stride = MIN_TRANSFER_STRIDE; // subdivide range&&&&&&&&if (nextTab == null) {&&&&&&&&&&& // initiating&&&&&&&&&&&&try {&&&&&&&&&&&&&&&&@SuppressWarnings("unchecked")&&&&&&&&&&&&&&&&Node&K,V&[] nt = (Node&K,V&[])new Node&?,?&[n && 1];&&&&&&& //构建一个nextTable对象，其容量为原来容量的两倍&&&&&&&&&&&&&&&&nextTab =&&&&&&&&&&&&} catch (Throwable ex) {&&&&& // try to cope with OOME&&&&&&&&&&&&&&&&sizeCtl = Integer.MAX_VALUE;&&&&&&&&&&&&&&&&return;&&&&&&&&&&&&}&&&&&&&&&&&&nextTable = nextT&&&&&&&&&&&&transferIndex =&&&&&&&&}&&&&&&&&int nextn = nextTab.&&&&&&&&// 连接点指针，用于标志位（fwd的hash值为-1，fwd.nextTable=nextTab）&&&&&&&&ForwardingNode&K,V& fwd = new ForwardingNode&K,V&(nextTab);&&&&&&&&// 当advance == true时，表明该节点已经处理过了&&&&&&&&boolean advance = true;&&&&&&&&boolean finishing = false; // to ensure sweep before committing nextTab&&&&&&&&for (int i = 0, bound = 0;;) {&&&&&&&&&&&&Node&K,V& int &&&&&&&&&&&&// 控制 --i ,遍历原hash表中的节点&&&&&&&&&&&&while (advance) {&&&&&&&&&&&&&&&&int nextIndex, nextB&&&&&&&&&&&&&&&&if (--i &= bound || finishing)&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&else if ((nextIndex = transferIndex) &= 0) {&&&&&&&&&&&&&&&&&&&&i = -1;&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&// 用CAS计算得到的transferIndex&&&&&&&&&&&&&&&&else if (U.compareAndSwapInt&&&&&&&&&&&&&&&&&&&&&&&&(this, TRANSFERINDEX, nextIndex,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&nextBound = (nextIndex & stride ?&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&nextIndex - stride : 0))) {&&&&&&&&&&&&&&&&&&&&bound = nextB&&&&&&&&&&&&&&&&&&&&i = nextIndex - 1;&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&if (i & 0 || i &= n || i + n &= nextn) {&&&&&&&&&&&&&&&&int &&&&&&&&&&&&&&&&// 已经完成所有节点复制了&&&&&&&&&&&&&&&&if (finishing) {&&&&&&&&&&&&&&&&&&&&nextTable = null;&&&&&&&&&&&&&&&&&&&&table = nextT&&&&&&& // table 指向nextTable&&&&&&&&&&&&&&&&&&&&sizeCtl = (n && 1) - (n &&& 1);&&&& // sizeCtl阈值为原来的1.5倍&&&&&&&&&&&&&&&&&&&&return;&&&& // 跳出死循环，&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&// CAS 更扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作&&&&&&&&&&&&&&&&if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {&&&&&&&&&&&&&&&&&&&&if ((sc - 2) != resizeStamp(n) && RESIZE_STAMP_SHIFT)&&&&&&&&&&&&&&&&&&&&&&&&return;&&&&&&&&&&&&&&&&&&&&finishing = advance = true;&&&&&&&&&&&&&&&&&&&&i = // recheck before commit&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&// 遍历的节点为null，则放入到ForwardingNode 指针节点&&&&&&&&&&&&else if ((f = tabAt(tab, i)) == null)&&&&&&&&&&&&&&&&advance = casTabAt(tab, i, null, fwd);&&&&&&&&&&&&// f.hash == -1 表示遍历到了ForwardingNode节点，意味着该节点已经处理过了&&&&&&&&&&&&// 这里是控制并发扩容的核心&&&&&&&&&&&&else if ((fh = f.hash) == MOVED)&&&&&&&&&&&&&&&&advance = true; // already processed&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&// 节点加锁&&&&&&&&&&&&&&&&synchronized (f) {&&&&&&&&&&&&&&&&&&&&// 节点复制工作&&&&&&&&&&&&&&&&&&&&if (tabAt(tab, i) == f) {&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V& ln,&&&&&&&&&&&&&&&&&&&&&&&&// fh &= 0 ,表示为链表节点&&&&&&&&&&&&&&&&&&&&&&&&if (fh &= 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 构造两个链表& 一个是原链表& 另一个是原链表的反序排列&&&&&&&&&&&&&&&&&&&&&&&&&&&&int runBit = fh &&&&&&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V& lastRun =&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& p = f. p != null; p = p.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int b = p.hash &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (b != runBit) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&runBit =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&lastRun =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (runBit == 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = lastR&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = lastR&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& p = p != lastR p = p.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int ph = p. K pk = p. V pv = p.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((ph & n) == 0)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = new Node&K,V&(ph, pk, pv, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = new Node&K,V&(ph, pk, pv, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在nextTable i 位置处插上链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在nextTable i + n 位置处插上链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i + n, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在table i 位置处插上ForwardingNode 表示该节点已经处理过了&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(tab, i, fwd);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// advance = true 可以执行--i动作，遍历节点&&&&&&&&&&&&&&&&&&&&&&&&&&&&advance = true;&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&// 如果是TreeBin，则按照红黑树进行处理，处理逻辑与上面一致&&&&&&&&&&&&&&&&&&&&&&&&else if (f instanceof TreeBin) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeBin&K,V& t = (TreeBin&K,V&)f;&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& lo = null, loTail = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& hi = null, hiTail = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&int lc = 0, hc = 0;&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& e = t. e != null; e = e.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int h = e.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& p = new TreeNode&K,V&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(h, e.key, e.val, null, null);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((h & n) == 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((p.prev = loTail) == null)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&lo =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loTail.next =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loTail =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((p.prev = hiTail) == null)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hi =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hiTail.next =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hiTail =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 扩容后树节点个数若&=6，将树转链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = (lc &= UNTREEIFY_THRESHOLD) ? untreeify(lo) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(hc != 0) ? new TreeBin&K,V&(lo) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = (hc &= UNTREEIFY_THRESHOLD) ? untreeify(hi) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(lc != 0) ? new TreeBin&K,V&(hi) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i + n, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(tab, i, fwd);&&&&&&&&&&&&&&&&&&&&&&&&&&&&advance = true;&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&}
其实helpTransfer（）方法的目的就是调用多个工作线程一起帮助进行扩容，这样的效率就会更高，而不是只有检查到要扩容的那个线程进行扩容操作，其他线程就要等待扩容操作完成才能工作既然这里涉及到扩容的操作，我们也一起来看看扩容方法transfer（）
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152private final void transfer(Node&K,V&[] tab, Node&K,V&[] nextTab) {&&&&&&&&int n = tab.length,&&&&&&&&// 每核处理的量小于16，则强制赋值16&&&&&&&&if ((stride = (NCPU & 1) ? (n &&& 3) / NCPU : n) & MIN_TRANSFER_STRIDE)&&&&&&&&&&&&stride = MIN_TRANSFER_STRIDE; // subdivide range&&&&&&&&if (nextTab == null) {&&&&&&&&&&& // initiating&&&&&&&&&&&&try {&&&&&&&&&&&&&&&&@SuppressWarnings("unchecked")&&&&&&&&&&&&&&&&Node&K,V&[] nt = (Node&K,V&[])new Node&?,?&[n && 1];&&&&&&& //构建一个nextTable对象，其容量为原来容量的两倍&&&&&&&&&&&&&&&&nextTab =&&&&&&&&&&&&} catch (Throwable ex) {&&&&& // try to cope with OOME&&&&&&&&&&&&&&&&sizeCtl = Integer.MAX_VALUE;&&&&&&&&&&&&&&&&return;&&&&&&&&&&&&}&&&&&&&&&&&&nextTable = nextT&&&&&&&&&&&&transferIndex =&&&&&&&&}&&&&&&&&int nextn = nextTab.&&&&&&&&// 连接点指针，用于标志位（fwd的hash值为-1，fwd.nextTable=nextTab）&&&&&&&&ForwardingNode&K,V& fwd = new ForwardingNode&K,V&(nextTab);&&&&&&&&// 当advance == true时，表明该节点已经处理过了&&&&&&&&boolean advance = true;&&&&&&&&boolean finishing = false; // to ensure sweep before committing nextTab&&&&&&&&for (int i = 0, bound = 0;;) {&&&&&&&&&&&&Node&K,V& int &&&&&&&&&&&&// 控制 --i ,遍历原hash表中的节点&&&&&&&&&&&&while (advance) {&&&&&&&&&&&&&&&&int nextIndex, nextB&&&&&&&&&&&&&&&&if (--i &= bound || finishing)&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&else if ((nextIndex = transferIndex) &= 0) {&&&&&&&&&&&&&&&&&&&&i = -1;&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&// 用CAS计算得到的transferIndex&&&&&&&&&&&&&&&&else if (U.compareAndSwapInt&&&&&&&&&&&&&&&&&&&&&&&&(this, TRANSFERINDEX, nextIndex,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&nextBound = (nextIndex & stride ?&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&nextIndex - stride : 0))) {&&&&&&&&&&&&&&&&&&&&bound = nextB&&&&&&&&&&&&&&&&&&&&i = nextIndex - 1;&&&&&&&&&&&&&&&&&&&&advance = false;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&if (i & 0 || i &= n || i + n &= nextn) {&&&&&&&&&&&&&&&&int &&&&&&&&&&&&&&&&// 已经完成所有节点复制了&&&&&&&&&&&&&&&&if (finishing) {&&&&&&&&&&&&&&&&&&&&nextTable = null;&&&&&&&&&&&&&&&&&&&&table = nextT&&&&&&& // table 指向nextTable&&&&&&&&&&&&&&&&&&&&sizeCtl = (n && 1) - (n &&& 1);&&&& // sizeCtl阈值为原来的1.5倍&&&&&&&&&&&&&&&&&&&&return;&&&& // 跳出死循环，&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&// CAS 更扩容阈值，在这里面sizectl值减一，说明新加入一个线程参与到扩容操作&&&&&&&&&&&&&&&&if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {&&&&&&&&&&&&&&&&&&&&if ((sc - 2) != resizeStamp(n) && RESIZE_STAMP_SHIFT)&&&&&&&&&&&&&&&&&&&&&&&&return;&&&&&&&&&&&&&&&&&&&&finishing = advance = true;&&&&&&&&&&&&&&&&&&&&i = // recheck before commit&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&&&&&// 遍历的节点为null，则放入到ForwardingNode 指针节点&&&&&&&&&&&&else if ((f = tabAt(tab, i)) == null)&&&&&&&&&&&&&&&&advance = casTabAt(tab, i, null, fwd);&&&&&&&&&&&&// f.hash == -1 表示遍历到了ForwardingNode节点，意味着该节点已经处理过了&&&&&&&&&&&&// 这里是控制并发扩容的核心&&&&&&&&&&&&else if ((fh = f.hash) == MOVED)&&&&&&&&&&&&&&&&advance = true; // already processed&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&// 节点加锁&&&&&&&&&&&&&&&&synchronized (f) {&&&&&&&&&&&&&&&&&&&&// 节点复制工作&&&&&&&&&&&&&&&&&&&&if (tabAt(tab, i) == f) {&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V& ln,&&&&&&&&&&&&&&&&&&&&&&&&// fh &= 0 ,表示为链表节点&&&&&&&&&&&&&&&&&&&&&&&&if (fh &= 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 构造两个链表& 一个是原链表& 另一个是原链表的反序排列&&&&&&&&&&&&&&&&&&&&&&&&&&&&int runBit = fh &&&&&&&&&&&&&&&&&&&&&&&&&&&&&Node&K,V& lastRun =&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& p = f. p != null; p = p.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int b = p.hash &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (b != runBit) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&runBit =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&lastRun =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&if (runBit == 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = lastR&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = lastR&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& p = p != lastR p = p.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int ph = p. K pk = p. V pv = p.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((ph & n) == 0)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = new Node&K,V&(ph, pk, pv, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = new Node&K,V&(ph, pk, pv, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在nextTable i 位置处插上链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在nextTable i + n 位置处插上链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i + n, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 在table i 位置处插上ForwardingNode 表示该节点已经处理过了&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(tab, i, fwd);&&&&&&&&&&&&&&&&&&&&&&&&&&&&// advance = true 可以执行--i动作，遍历节点&&&&&&&&&&&&&&&&&&&&&&&&&&&&advance = true;&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&// 如果是TreeBin，则按照红黑树进行处理，处理逻辑与上面一致&&&&&&&&&&&&&&&&&&&&&&&&else if (f instanceof TreeBin) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeBin&K,V& t = (TreeBin&K,V&)f;&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& lo = null, loTail = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& hi = null, hiTail = null;&&&&&&&&&&&&&&&&&&&&&&&&&&&&int lc = 0, hc = 0;&&&&&&&&&&&&&&&&&&&&&&&&&&&&for (Node&K,V& e = t. e != null; e = e.next) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&int h = e.&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& p = new TreeNode&K,V&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(h, e.key, e.val, null, null);&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((h & n) == 0) {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((p.prev = loTail) == null)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&lo =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loTail.next =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&loTail =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else {&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&if ((p.prev = hiTail) == null)&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hi =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hiTail.next =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&hiTail =&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&++&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&&&&&&&&&// 扩容后树节点个数若&=6，将树转链表&&&&&&&&&&&&&&&&&&&&&&&&&&&&ln = (lc &= UNTREEIFY_THRESHOLD) ? untreeify(lo) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(hc != 0) ? new TreeBin&K,V&(lo) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&hn = (hc &= UNTREEIFY_THRESHOLD) ? untreeify(hi) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(lc != 0) ? new TreeBin&K,V&(hi) :&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i, ln);&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(nextTab, i + n, hn);&&&&&&&&&&&&&&&&&&&&&&&&&&&&setTabAt(tab, i, fwd);&&&&&&&&&&&&&&&&&&&&&&&&&&&&advance = true;&&&&&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&}
扩容过程有点复杂，这里主要涉及到多线程并发扩容,ForwardingNode的作用就是支持扩容操作，将已处理的节点和空节点置为ForwardingNode，并发处理时多个线程经过ForwardingNode就表示已经遍历了，就往后遍历，下图是多线程合作扩容的过程：
介绍完扩容过程，我们再次回到put流程，在第四步中是向链表或者红黑树里加节点，到第五步，会调用treeifyBin（）方法进行链表转红黑树的过程
1234567891011121314151617181920212223242526272829private final void treeifyBin(Node&K,V&[] tab, int index) {&&&&Node&K,V& int n,&&&&if (tab != null) {&&&&&&&&//如果整个table的数量小于64，就扩容至原来的一倍，不转红黑树了&&&&&&&&//因为这个阈值扩容可以减少hash冲突，不必要去转红黑树&&&&&&&&if ((n = tab.length) & MIN_TREEIFY_CAPACITY) &&&&&&&&&&&&tryPresize(n && 1);&&&&&&&&else if ((b = tabAt(tab, index)) != null && b.hash &= 0) {&&&&&&&&&&&&synchronized (b) {&&&&&&&&&&&&&&&&if (tabAt(tab, index) == b) {&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& hd = null, tl = null;&&&&&&&&&&&&&&&&&&&&for (Node&K,V& e = e != null; e = e.next) {&&&&&&&&&&&&&&&&&&&&&&&&//封装成TreeNode&&&&&&&&&&&&&&&&&&&&&&&&TreeNode&K,V& p =&&&&&&&&&&&&&&&&&&&&&&&&&&&&new TreeNode&K,V&(e.hash, e.key, e.val,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&null, null);&&&&&&&&&&&&&&&&&&&&&&&&if ((p.prev = tl) == null)&&&&&&&&&&&&&&&&&&&&&&&&&&&&hd =&&&&&&&&&&&&&&&&&&&&&&&&else&&&&&&&&&&&&&&&&&&&&&&&&&&&&tl.next =&&&&&&&&&&&&&&&&&&&&&&&&tl =&&&&&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&&&&&&&&//通过TreeBin对象对TreeNode转换成红黑树&&&&&&&&&&&&&&&&&&&&setTabAt(tab, index, new TreeBin&K,V&(hd));&&&&&&&&&&&&&&&&}&&&&&&&&&&&&}&&&&&&&&}&&&&}}
到第六步表示已经数据加入成功了，现在调用addCount()方法计算ConcurrentHashMap的size，在原来的基础上加一，现在来看看addCount()方法
1234567891011121314151617181920212223242526272829303132333435363738394041private final void addCount(long x, int check) {&&&&CounterCell[] long b,&&&&//更新baseCount，table的数量，counterCells表示元素个数的变化&&&&if ((as = counterCells) != null ||&&&&&&&&!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {&&&&&&&&CounterC long v; int m;&&&&&&&&boolean uncontended = true;&&&&&&&&//如果多个线程都在执行，则CAS失败，执行fullAddCount，全部加入count&&&&&&&&if (as == null || (m = as.length - 1) & 0 || &&&&&&&&&&&&(a = as[ThreadLocalRandom.getProbe() & m]) == null ||&&&&&&&&&&&&!(uncontended =&&&&&&&&&&&&&&<pareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {&&&&&&&&&&&&fullAddCount(x, uncontended);&&&&&&&&&&&&return;&&&&&&&&}&&&&&&&&if (check &= 1)&&&&&&&&&&&&return;&&&&&&&&s = sumCount();&&&&}&&&&&//check&=0表示需要进行扩容操作&&&&if (check &= 0) {&&&&&&&&Node&K,V&[] tab, int n,&&&&&&&&while (s &= (long)(sc = sizeCtl) && (tab = table) != null &&&&&&&&&&&&&&&&&(n = tab.length) & MAXIMUM_CAPACITY) {&&&&&&&&&&&&int rs = resizeStamp(n);&&&&&&&&&&&&if (sc & 0) {&&&&&&&&&&&&&&&&if ((sc &&& RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||&&&&&&&&&&&&&&&&&&&&sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||&&&&&&&&&&&&&&&&&&&&transferIndex &= 0)&&&&&&&&&&&&&&&&&&&&break;&&&&&&&&&&&&&&&&if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))&&&&&&&&&&&&&&&&&&&&transfer(tab, nt);&&&&&&&&&&&&}&&&&&&&&&&&&//当前线程发起库哦哦让操作，nextTable=null&&&&&&&&&&&&else if (U.compareAndSwapInt(this, SIZECTL, sc,&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&(rs && RESIZE_STAMP_SHIFT) + 2))&&&&&&&&&&&&&&&&transfer(tab, null);&&&&&&&&&&&&s = sumCount();&&&&&&&&}&&&&}}
put的流程现在已经分析完了，你可以从中发现，他在并发处理中使用的是乐观锁，当有冲突的时候才进行并发处理，而且流程步骤很清晰，但是细节设计的很复杂，毕竟多线程的场景也复杂
我们现在要回到开始的例子中，我们对个人信息进行了新增之后，我们要获取所新增的信息，使用String name = map.get(“name”)获取新增的name信息，现在我们依旧用debug的方式来分析下ConcurrentHashMap的获取方法get()
123456789101112131415161718192021public V get(Object key) {&&&&Node&K,V&[] Node&K,V& e, int n, K&&&&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.&&&&&&&&}&&&&&&&&//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.&&&&&&&&}&&&&}&&&&return null;}
ConcurrentHashMap的get操作的流程很简单，也很清晰，可以分为三个步骤来描述
计算hash值，定位到该table索引位置，如果是首节点符合就返回
如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null
最后我们来看下例子中最后获取size的方式int size = map.size();，现在让我们看下size()方法
1234567891011121314151617public int size() {&&&&long n = sumCount();&&&&return ((n & 0L) ? 0 :&&&&&&&&&&&&(n & (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :&&&&&&&&&&&&(int)n);}final long sumCount() {&&&&CounterCell[] as = counterC CounterC //变化的数量&&&&long sum = baseC&&&&if (as != null) {&&&&&&&&for (int i = 0; i & as. ++i) {&&&&&&&&&&&&if ((a = as[i]) != null)&&&&&&&&&&&&&&&&sum += a.&&&&&&&&}&&&&}&&&&return }
在JDK1.8版本中，对于size的计算，在扩容和addCount()方法就已经有处理了，JDK1.7是在调用size()方法才去计算，其实在并发集合中去计算size是没有多大的意义的，因为size是实时在变的，只能计算某一刻的大小，但是某一刻太快了，人的感知是一个时间段，所以并不是很精确
总结与思考
其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言，总结如下思考
JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）
JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档
JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，我觉得有以下几点
因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然
在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据
TA的最新馆藏
喜欢该文的人也喜欢