ConcurrentHashMap的图解分析、特有节点、put方法解析、树的读写锁(find方法和putTreeVal)、总结与hashMap的核心区别

n |= n >>> 1; n = n | n >>> 1;

红黑树：TreeNode节点：没有线程安全措施。但是主要靠TreeBin(通过volatile修饰首节点和等待线程以及红黑树的锁状态。)来保证线程安全的。

标识是否查询到要放的元素boolean searched = false;

ConcurrentHashMap-put：树的写操作java.util.concurrent.ConcurrentHashMap.TreeBin#putTreeVal(涉及到锁)

boolean waiting = false;

n>>>2位运算的结果就是n的二进制向右偏移两位。相当于除以4。为了防止直接乘以0.75产生小数，直接用位运算，这样就是n-n的四分之一的整数位

while ((tab = table) == null || tab.length == 0)

//加锁lockRoot();

定义的特殊hash值：

else if (ph < h)

while ((e = e.next) != null) { if (e.hash == h&&((ek = e.key) == key || (ek != null && key.equals(ek))))                    return e.val;            }

判断是否有其他线程在对当前hash表进行初始化

Node

onlyIfAbsent默认为falseoldVal = e.val;if (!onlyIfAbsent)e.val =value; break;

再次比较key与当前索引位上的key相等

root

;;类似于while(true)int binCount = 1;for (int b=2;; ++binCount){     System.out.println(binCount); //累加的值     System.out.println(b);//2}

测试代码：long a=0;for (int i = Integer.MIN_VALUE; i < Integer.MAX_VALUE; i++) {\ta++;\tint n=i;\tn |= n >>> 1;\tn |= n >>> 2;\tn |= n >>> 4;\tn |= n >>> 8;\tn |= n >>> 16;\t//& 两者都为1才是1，有0结果一定是0. 所有奇数与0000...0001进行&运算，结果一定是1.\t//所有偶数与0000...0001进行&运算，结果一定是0// if ((n&1)==1){//找奇数//// System.out.println(n);//// }\tif ((n&1)==0){//找偶数\t\tSystem.out.println(\"@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@\"+n);\t}\tSystem.out.print(i);\tSystem.out.print(\"==>\");\tSystem.out.print(n);\tSystem.out.println();//通过打印i==>n，发现，所有的负数都会转成-1.正数结果从3开始二倍增长。4-1===》8-1==》16-1==》2的n次方-1}System.out.println(a);System.out.println(a-Integer.MAX_VALUE-Integer.MAX_VALUE);

再次确认hash表没有被其他线程初始化

2、如果当前锁状态不是等待或者写锁，也就是说当前锁状态为并发线程读锁

写锁0001&0010=0读锁最小是4，每多一个线程再加44&0010=0100&0010=08&0010=1000&0010=012&0010=1100&0010=016及以上后四位都是0了，得到的结果肯定是0

对于指定的。指定是1的时候，参考前面的构造解析，最后结果也是2-2的四分之一的整数位也就是0

int n = c - 1;n |= n >>> 1;n |= n >>> 2;n |= n >>> 4;n |= n >>> 8;n |= n >>> 16;|运算：有1则结果为1通过将n与多个右移后的结果进行|运算，保证当前数的二进制数最后一位是1，成为奇数。当没有超过最大值时，最终返回的n+1一定是偶数。并且是2 的指数次幂。return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

int n = (sc > 0) ? sc : DEFAULT_CAPACITY;

标识：当前map的状态，初始化、是否并发、扩容

????这里的逻辑没有太搞清楚

xp.right = x;

比较类的className

如果比较不出来，可能是对象，因此比对class对

定位好要放的空节点的位置赋值给p

TreeNode

判断是否是正在扩容索引位上有元素的，判断当前元素是否是forwarding nodes，即当前元素的hash是否是-1

oldVal = p.val; if (!onlyIfAbsent) p.val = value;

return p;

ConcurrentHashMap：get方法(重点是ConcurrentHashMap.TreeBin的find方法，涉及到锁)

Y

else

//小于0代表新节点的hash小于root，放在root的左边xp.left = x;

N已经初始化的表，要要根据元素的hash计算出索引，再获取对应索引的元素是否为空

if (oldVal != null)    return oldVal;break;

核心属性变量

fh >= 0

通过传的要put的节点的hash、k和v来创建新节点，指定新节点的next为空节点f，父节点为xp(root节点)

if ((ek = e.key) == key || (ek != null && key.equals(ek)))

状态不为0，调用contendedLock

2、红黑树

分析当前锁的状态。0是无锁，二进制0000  ：无锁状态在上一步就返回了这里会出现的状态：static final int WRITER = 1; //写锁，二进制0001static final int WAITER = 2;//等待获取写锁的状态，二进制0010static final int READER = 4;//并发读锁，二进制0100，设置读取锁定的增量值，每多一个线程获取读锁就加4

前面直接比较比不出来结果的情况下，到这里如果新元素class为null(不是String，也不是接口或接口的实现类)，或者新元素和root的class是不一样

//如果获取的索引位的hash值等于key的hashif ((eh = e.hash) == h)

else if ((ph = p.hash) > h)

putTreeVa见后面专门对写操作的详解l

如果是放置到红黑树上，就不用再树化了，因此上面将binCount赋值为2。

static final int MOVED     = -1; // hash for forwarding nodes    static final int TREEBIN   = -2; // hash for roots of trees    static final int RESERVED  = -3; // hash for transient reservations    static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash

测试代码文字版

//这个树都是这个新节点f.prev = x;

返回对应的value

private static final int tableSizeFor(int c) {        int n = c - 1;        n |= n >>> 1;        n |= n >>> 2;        n |= n >>> 4;        n |= n >>> 8;        n |= n >>> 16;        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;    }

if (f != null)

ConcurrentHashMap cp1=new ConcurrentHashMap(1);

在红黑树中进行左右递归查询

else if ((s & WAITER) == 0)

sizeCtl = sc;

如果为null，代表这个元素已插入到树中

ConcurrentHashMap：put方法

map的内部字段table指向新建的hash表

图解ConcurrentHashMap

说明这个元素此时就是要找的元素

获取原索引位的老值，赋值给f

hash小于0，说明索引位上的元素是特别的那几个节点，TreeBin/forwarding Node/ReservationNode占位结点

else if (eh < 0)

如果没有被其他线程修改，正常是走到这里，将查询转移到站位节点的next，也就是扩容后的新表里查询

else if ((pk = p.key) == k || (pk != null && k.equals(pk)))

LOCKSTATE = U.objectFieldOffset(k.getDeclaredField(\"lockState\"));

初始化为0，在hash表初始化、直接放置到数组上的、其他线程正在扩容的，这三种情况下不会对binCount进行赋值，走到这还是等于0，，因此不需要判断是否要树化

首先上锁synchronized (f)

1：hash和key都相同，根据传来的是否覆盖的标识onlyIfAbsent来决定是否替换老值

链表:Node节点：key和hash值都用final修饰保证线程安全；next指向和value是通过volatile修饰保证线程可见性；

p == null

结论

N

如果上面的条件都不满足：代表索引上有真实元素，就要按情况区分：链表还是红黑树

if ((tab = table) == null || tab.length == 0)

finally

即状态为写锁或者等待获取写锁状态时，满足运算结果不为0

next

root的hash小于新元素，新元素在右边

根据hash判断是红黑树还是链表

构造方法

首先获取key的hashint hash = spread(key.hashCode());

如果root和新元素的key相等，代表查询到了直接返回

N:再判断是否是TreeBin

不为空，代表找到key相同的，再判断是否要覆盖

计数和扩容的代码块：1、维护集合的长度。2、当超过阈值时进行扩容。

如果还是相等，再调用本地方法的比较方法：比较hash值和代表对象的引用地址

最后还是没找到的，那一定是链表了，直接按链表查询返回

根据根节点标识-red属性(是否是红节点)红黑树中，根节点都是黑节点，子节点都是红节点。如果xp是黑节点，在黑节点下加一个红节点不会影响红黑树的结构变化，直接设置新节点为红节点即可。如果xp不是黑节点，那在黑节点下新增节点，必然会导致红黑树自旋，导致树的结构变化(可能是结构变化，也可能是红变黑的变化)，因此要获取写锁后，再进行平衡插入(自旋插入)。

TreeBin是一种代理节点，其连着红黑树的结点TreeNode，选择用一个代理节点包含复杂的红黑树操作，并且提供加锁和解锁的方法。

计算出key对应的索引位置，获取这个位置是否已经存在值了

ConcurrentHashMap是在第一次放元素的时候才进行初始化的判断table是否未初始化

break;

dir = 1;

链表循环时，记录链表元素的总个数。后面用来判断是否要树化

判断节点位置

判断是否要树化if (binCount >= TREEIFY_THRESHOLD)

binCount != 0

if (dir <= 0)

写锁：s | WAITER=0001 | 0010 =0011=3读锁最小是4，每多一个线程再加44 | WAITER=0100 | 0010 =0110=6=2+2的2次方8|0010=1000&0010=1010=10=2+2的3次方12|0010=1100|0010=1110==2+2的4次方16及以上后都是在0010的基础上加了2的n次方。最终的结果都是以10结尾的二进制数，等再次循环时，与&WAITER(0010)的结果肯定不为0。写锁：0011& ~WAITER(1101)=0001读锁：0110& ~WAITER(1101)=0100=41010& ~WAITER(1101)=1000=81110& ~WAITER(1101)=1100=10

e.hash == hash && ((ek = e.key) == key ||(ek != null && ey.equals(ek)))

tab = initTable();

核心，这里就是与hashMap不同的地方。

对于没有指定map容量的无参构造创建的map，默认是16(2的4次方)。后面每次扩容后就是2的4+i次方。这里sc计算的结果就是n的0.75。

if (((s = lockState) & ~WAITER) == 0)

表初始化和调整大小控件。如果为负数，则表正在初始化或调整大小：-1表示初始化，否则-（1+活动的调整大小线程数）比如-5代表四个线程并发的进行初始化或者扩容。如果是正数和0，代表hash表还没有被初始化，即table为null，将保留创建时要使用的初始表大小，默认值为0。初始化后，保存下一个要调整表大小的元素计数值。

按上面的判断，将新节点初始化

不会到这里

走到这里，代表还没有初始化，因此上一步sc=sizeCtl时，sizeCtl还存的是hash表的初始容量，因此在这里要判断设置的初始化容量是否大于0，大于0就直接用，否则就使用默认值16

waiting改为true的，代表map的等待线程已被其他线程占有，当前线程挂起

//root为黑节点，那新加的节点就是红色x.red = true;

计算出下次的阈值：size的0.75

尾部插入

if (a == null || b == null || (d = a.getClass().getName(). compareTo(b.getClass().getName())) == 0)

小于0代表已经被其他线程占了，调用yield方法(给调度程序的提示，表明当前线程愿意放弃其当前对处理器的使用。)由其他线程来完成初始化。 Thread.yield();

相当于锁住了该hash表

这类元素不能确定到底是在左边还是右边，就需要左右都找

(e = e.next) == null

table

类型一样

针对不同的节点，都有自己对find的实现

该方法如何计算出合适的表空间大小的

&0010为0的只有写锁和读锁，这里代表有线程占有读或者写锁|：只要有1就为1，都是0才为0

return e.val;

return q;

return d;

sc = n - (n >>> 2);

ReservationNode占位结点

源码注释

//当前searched为false，只有在进行了左右查询后才改为true，代表整个树都查过了if (!searched)

如果找到了返回

private transient volatile int sizeCtl;

如果没找到，调用深层次的比较方法

Y：代表在扩容，调用协助其扩容的方法

Y：链表。hash小于0的特殊节点见前面的核心属性变量-定义的特殊hash值

int binCount = 0;

root节点不为空时，比较hash值，判断新元素在root的左还是右

TreeBin

常用于compute和computeIfAbsent操作

root的hash大于新元素，新元素在左边

public ConcurrentHashMap(int initialCapacity) {        if (initialCapacity < 0)            throw new IllegalArgumentException();//如果大于等于2的29次方，就直接赋值给2的30次方        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?                   MAXIMUM_CAPACITY ://如果小于2的29次方，就使用入参initialCapacity创建                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));        this.sizeCtl = cap;    } 

else if ((fh = f.hash) == MOVED)

ConcurrentHashMap

else

int MAXIMUM_CAPACITY = 1 << 30;2的30次方右移一位后：正数：偶数2的n次方-->2的n+1次方                                     奇数2的n次方-1-->2的n+1次方-1

for循环

LockSupport.park(this);

if (tab == null || (n = tab.length) == 0)

ForwardingNode

&1101为0的只有0010即等待获取写锁状态

dir = -1;

代表树中原来有root，就需要根据dir来判断新节点x放在root的左边还是右边

else if (f instanceof TreeBin)

if (!xp.red)

static final int WRITER = 1; //写锁，二进制0001static final int WAITER = 2;//等待获取写锁的状态，二进制0010static final int READER = 4;//并发读锁，二进制0100，设置读取锁定的增量值，每多一个线程获取读锁就加4

if ((sc = sizeCtl) < 0)

n就是在既大于等于initialCapacity，又是2的指数幂中找最近的数作为n。比如c是1：1是2的0次幂，n=1c是2：2是2的1次幂，n=2c是3：大于等于3的最近的是4，n=4

return tab;

可以根据这个网站来通过动画的方式理解，https://www.cs.usfca.edu/~galles/visualization/RedBlack.html插入1，再放2的时候，1 是黑节点，放2不会引起红黑树变化；再放3，就是放在2的右侧，2是红节点，就会导致红黑树自旋，结构发生变化。再放4的时候，3是红节点，但是平衡没有被打破，因此只会发生颜色变化。

总结与hashmap核心区别：线程安全

通过cas先修改sizeCtl的值为-1，代表当前hash表已经被占，有该线程完成对其的初始化。如果修改失败代表并发其他线程通过cas修改了sizeCtl，由其他线程完成对其初始化操作

binCount = 2;

1、如果当前锁状态不是等待或者写锁，就直接按链表的方式比较key进行查询

进入for循环for (int s;;)

else if (waiting)

d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);

Y：通过cas将元素放到对应索引位上，成功跳出循环，失败再次循环

1、链表

for循环：比对元素

如果发生变化了，不处理

//空参构造，方法体什么都没有做：因为要保证线程安全，只有在线程向map中第一次放值时，才会进行初始化public ConcurrentHashMap() {   } 

tableSizeFor

table = tab = nt;

一个特殊的Node结点，hash为-1，key与val都为null。

//计算要找的key的hash int h = spread(key.hashCode());

ConcurrentHashMap的图解分析、特有节点、put方法解析、树的读写锁(find方法和putTreeVal)、总结与hashMap的核心区别

确定了hash表的size，就可以创建hash表了

binCount = 1;