HashMap
public V put(K var1, V var2) { return this.putVal(hash(var1), var1, var2, false, true); } final V putVal(int var1, K var2, V var3, boolean var4, boolean var5) { HashMap.Node[] var6; int var8; if ((var6 = this.table) == null || (var8 = var6.length) == 0) { var8 = (var6 = this.resize()).length; } Object var7; int var9; if ((var7 = var6[var9 = var8 - 1 & var1]) == null) { var6[var9] = this.newNode(var1, var2, var3, (HashMap.Node)null); } else { Object var10; Object var11; if (((HashMap.Node)var7).hash == var1 && ((var11 = ((HashMap.Node)var7).key) == var2 || var2 != null && var2.equals(var11))) { var10 = var7; } else if (var7 instanceof HashMap.TreeNode) { var10 = ((HashMap.TreeNode)var7).putTreeVal(this, var6, var1, var2, var3); } else { int var12 = 0; while(true) { if ((var10 = ((HashMap.Node)var7).next) == null) { ((HashMap.Node)var7).next = this.newNode(var1, var2, var3, (HashMap.Node)null); if (var12 >= 7) { this.treeifyBin(var6, var1); } break; } if (((HashMap.Node)var10).hash == var1 && ((var11 = ((HashMap.Node)var10).key) == var2 || var2 != null && var2.equals(var11))) { break; } var7 = var10; ++var12; } } if (var10 != null) { Object var13 = ((HashMap.Node)var10).value; if (!var4 || var13 == null) { ((HashMap.Node)var10).value = var3; } this.afterNodeAccess((HashMap.Node)var10); return var13; } } ++this.modCount; if (++this.size > this.threshold) { this.resize(); } this.afterNodeInsertion(var5); return null; }put()
1 数组为空或者数组长度为0，对数组进行初始化
2 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)，hash值进行二次加工（对hash值的高16位和低16进行异或，使得hash值更加散列）
3 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)
① 如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null； ② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作 ③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样： 如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null； 如果该链表已经有这个节点了，那么找到該节点并更新新数据，返回老数据。树化 1 如果链表长度 > 8 ， 执行树化方法 2 如果Node数组长度 < 64 , 对Node数组进行扩容 3 如果Node数组长度 > 64 , 1 判断链表的根节点是否为空，如果不为空，声明树节点 2 遍历链表，对每一个链表节点改造为双向链表再改造为树节点 3 遍历双向链表改为红黑树
扩容 1 如果数组长度大于阈值（数组长度 * 加载因子），执行扩容方法 2 数组长度扩大两倍（左移一位），并且算出加载因子 3 如果下标处是节点，则重新计算下标并赋值 4 如果下标处是链表，则对链表的每一个节点的hash值进行计算 （key.hash & 新数组长度），形成高低两个链表，低位链在原下标处，高位链在（原数组长度+下标）处 5 如果下标处是TreeNode（红黑树），则对双向链表（红黑树结构底层还维持着双向链表）的每一个节点的hash值进行计算（key.hash & 新数组长度），形成高低两个链表，判断两个链表的长度，如果链表的长度 > = 6 ，直接将双向链表改为红黑树，放到数组下标处，否则，将双向链表改为单向链表，放到数组下标处 低位链在原下标处，高位链在（原数组长度+下标）处， 总结 1 数据结构： 数组 链表 红黑树 2 默认数组长度 16 ，加载因子 0.75 3 如果链表节点数 >= 8 进行树化 4 如果数组长度 >= 64 ,链表节点数 >= 8 进行树化 5 如果数组长度 >= 64 ,链表节点数 < 8 进行树退化 6 如果数组长度 < 64 ,链表节点数 >= 8 进行扩容
ConcurrentHashMap
1 JDK1.8中的并发安全主要由CAS操作 和 Synchronized关键字完成
2 Synchronized关键字主要用于操作某个位置时进行加锁（该位置不为空），如链表上插入节点，或者红黑树中插入节点
put()方法
final V putVal(K var1, V var2, boolean var3) { if (var1 != null && var2 != null) { 1 int var4 = spread(var1.hashCode()); int var5 = 0; ConcurrentHashMap.Node[] var6 = this.table; while(true) { int var8; while(var6 == null || (var8 = var6.length) == 0) { 2 var6 = this.initTable(); } ConcurrentHashMap.Node var7; int var9; if ((var7 = tabAt(var6, var9 = var8 - 1 & var4)) == null) { 3 if (casTabAt(var6, var9, (ConcurrentHashMap.Node)null, new ConcurrentHashMap.Node(var4, var1, var2, (ConcurrentHashMap.Node)null))) { break; } } else { 4 int var10; if ((var10 = var7.hash) == -1) { var6 = this.helpTransfer(var6, var7); } else { Object var11 = null; synchronized(var7) { 5 if (tabAt(var6, var9) == var7) { if (var10 < 0) { if (var7 instanceof ConcurrentHashMap.TreeBin) { var5 = 2; ConcurrentHashMap.TreeNode var18; if ((var18 = ((ConcurrentHashMap.TreeBin)var7).putTreeVal(var4, var1, var2)) != null) { var11 = var18.val; if (!var3) { var18.val = var2; } } } } else { label103: { var5 = 1; ConcurrentHashMap.Node var13; Object var14; for(var13 = var7; var13.hash != var4 || (var14 = var13.key) != var1 && (var14 == null || !var1.equals(var14)); ++var5) { ConcurrentHashMap.Node var15 = var13; if ((var13 = var13.next) == null) { var15.next = new ConcurrentHashMap.Node(var4, var1, var2, (ConcurrentHashMap.Node)null); break label103; } } var11 = var13.val; if (!var3) { var13.val = var2; } } } } } if (var5 != 0) { if (var5 >= 8) { 6 this.treeifyBin(var6, var9); } if (var11 != null) { return var11; } break; } } } } this.addCount(1L, var5); 7 return null; } else { throw new NullPointerException(); } }1 如果Key和Value 都不等于Null，那么就对Key.hasCode进行再一次加工（高16位异或低16与长整型的最大值）， 使hash值更加散列，减少hash冲突 否则报NPE
2 如果数组为nulll或者数组长度为0，就初始化数组
3 通过index = （n-1）& hash ，取得下标后看此处的节点是否为空，如果为null ，把key value构造为一个节点类型并且利用CAS操作把此节点方法下标处，自旋保证成功。
4 如果下标处有数据，
4.1 如果检测到fh = f.hash == -1，则f是ForwardingNode节点，表示有其他线程正在进行扩容操作，则帮助线程一起进行扩容操作
4.2 否则使用Synchronized 加锁
5 加锁成功后
5.1 对下标节点进行判断，如果是TreeBin ，就写入红黑树节点 5.2 如果是Node，并且遍历链表，key不等，使用尾插法插入节点
6 添加成功后，如果数组长度 >= 64 ,链表节点数 >= 8 进行树化
7 执行addCount() , 作用：让ConcurrentHashMap中的元素加一 ，此操作也是并发操作，此操作之后会判断是否需要扩容，如果需要就进行扩容
1 扩容 概括版： (1)对于get读操作，如果当前节点有数据，还没迁移完成，此时不影响读，能够正常进行。 如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时get线程会帮助扩容。 (2)对于put/remove写操作，如果当前链表已经迁移完成，那么头节点会被设置成fwd节点，此时写线程会帮助扩容，如果扩容没有完成，当前链表的头节点会被锁住，所以写线程会被阻塞，直到扩容完成。
1 计算每个线程可以处理的桶区间 默认是16
2 初始化nextTable ， 扩容为原数组的2倍
单线程
3 先获取最右一个桶区间数组长度 i 和bound ， 再循环的从 bound 到 i 处获取数据进行比对
4 如果这个位置是空节点 ， 则把这个节点改为ForwardingNode节点
4 如果这个位置是Node节点，则重新计算下标放到nextTable中，转移完成之后把节点改为ForwardingNode节点
5 如果这个位置是链表节点 ， 则根据hash&新数组长度-1 ，得到高位链和低位链再进行移动 ， ，转移完成之后把节点改为ForwardingNode节点
6 如果这个位置是TreeBin节点 ， 则根据hash&新数组长度-1 ，得到高位链和低位链再进行移动 , 再判断是否需要进行树退化成单链表 ， ，转移完成之后把节点改为ForwardingNode节点
7 当完成当前桶区间的所有节点的转移之后 ， 把advance属性改为false ， 并计算下一个桶区间开启第一步
当完成数组所有节点的转移之后，会把finish属性改为true ，然后在判断是不是所有的线程都完成了转移 ， 再把nextTable赋值给table ，并且把sizeCtl的值赋值为新数组长度的0.75倍
多线程
3 从右向左每一个线程都计算出一个桶区间数组长度 i 和bound ， 再循环的从 bound 到 i 处获取数据进行比对 （每进入一个线程就会对sizeCtl属性加一） 每一个线程 4 - 7 4 如果这个位置是空节点 ， 则把这个节点改为ForwardingNode节点
4 如果这个位置是Node节点，则重新计算下标放到nextTable中，转移完成之后把节点改为ForwardingNode节点
5 如果这个位置是链表节点 ， 则根据hash&新数组长度-1 ，得到高位链和低位链再进行移动 ， ，转移完成之后把节点改为ForwardingNode节点
6 如果这个位置是TreeBin节点 ， 则根据hash&新数组长度-1 ，得到高位链和低位链再进行移动 , 再判断是否需要进行树退化成单链表 ， ，转移完成之后把节点改为ForwardingNode节点
7 当完成当前桶区间的所有节点的转移之后 ， 把advance属性改为false ， 并计算下一个桶区间开启第一步
8 计算桶区间之后，会对advance属性进行判断，是否有线程对此桶区间进行扩容，有则跳过
9 当一个线程没有桶区间进行转移时，会把finish属性改为true , 然后退到上一步的while循环进行阻塞，然后sizeCtl减一
10 当sizeCtl属性减为初始值时，标志着转移完成，然后把nextTable赋值给table ，并且把sizeCtl的值赋值为新数组长度的0.75倍
2 addCount（）
private final void addCount(long var1, int var3) { ConcurrentHashMap.CounterCell[] var4; long var5; long var7; int var12; if ((var4 = this.counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, var5 = this.baseCount, var7 = var5 + var1)) { boolean var13 = true; ConcurrentHashMap.CounterCell var9; long var10; if (var4 == null || (var12 = var4.length - 1) < 0 || (var9 = var4[ThreadLocalRandom.getProbe() & var12]) == null || !(var13 = U.compareAndSwapLong(var9, CELLVALUE, var10 = var9.value, var10 + var1))) { this.fullAddCount(var1, var13); return; } if (var3 <= 1) { return; } var7 = this.sumCount(); } int var11; ConcurrentHashMap.Node[] var14; if (var3 >= 0) { for(; var7 >= (long)(var12 = this.sizeCtl) && (var14 = this.table) != null && (var11 = var14.length) < 1073741824; var7 = this.sumCount()) { int var16 = resizeStamp(var11); if (var12 < 0) { ConcurrentHashMap.Node[] var15; if (var12 >>> RESIZE_STAMP_SHIFT != var16 || var12 == var16 + 1 || var12 == var16 + MAX_RESIZERS || (var15 = this.nextTable) == null || this.transferIndex <= 0) { break; } if (U.compareAndSwapInt(this, SIZECTL, var12, var12 + 1)) { this.transfer(var14, var15); } } else if (U.compareAndSwapInt(this, SIZECTL, var12, (var16 << RESIZE_STAMP_SHIFT) + 2)) { this.transfer(var14, (ConcurrentHashMap.Node[])null); } } } }有共享变量BASECOUNT和共享变量counterCells[ ] 共同来进行计数
1 第一次计数时，多个线程争抢BASECOUNT 的控制权，利用CAS操作保证线程安全 2 没有抢到控制权的线程，会用线程产生一个随机数并且与counterCells数组长度减 1 ，获得数组下标（index = ThreadLocalRandom.getProbe() & counterCells.length - 1）,在此下标处利用CAS操作进行加 1 操作
3 最后执行sumCount（） ， 把每一个的计数进行汇总
如果counterCells[ ] 数组为空，则先对BASECOUNT 的控制权进行争抢，否则直接进行定位，然后进行争抢控制权
总结 ： 采用分治的思想，对计数的线程数进行分离，让并发量降低
总结 1 数据结构： 数组 链表 红黑树 2 默认数组长度 16 ，加载因子 0.75 3 如果链表节点数 >= 8 进行树化 4 如果数组长度 >= 64 ,链表节点数 >= 8 进行树化 5 如果数组长度 >= 64 ,链表节点数 < 8 进行树退化 6 如果数组长度 < 64 ,链表节点数 >= 8 进行扩容
