HashMap的putVal方法和resize
声明
重要声明：由于本人内功不够，本文未有涉及红黑树如何添加元素，仅用简明思路和方法来了解HashMap的存值过程，备以今后面试等场景。以博客记之，便于后续翻阅，不适深究者
putVal 方法解析
其实HashMap的简单存储过程已经在前面一篇文章演示过了，这里主要是来看一下putVal方法。
首先，先看一下putVal方法的源码：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]
if ((p = tab[i = (n - 1) & hash]) == null)
//创建一个节点，放置在tab的第i个位置上。
tab[i] = newNode(hash, key, value, null);
else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
Node<K,V> e; K k;
//p就是冲突的第一个位置。hash值相同，key相同，或者equals。表示key相同。
//注意：相同的hash可能对应不同的key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD - 1 = 7 如果
//当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，
//链表存在的最长的串就是8个。
// 8个节点是一个临界值。
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;//同样，如果存在一样的key，则跳过
p = e;//相当于p=p.next
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
//如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
if (!onlyIfAbsent || oldValue == null)
e.value = value;//值覆盖
afterNodeAccess(e);
return oldValue;//返回oldValue
}
}
++modCount;//并发操作，fast-fail
if (++size > threshold)//size+1
resize();
afterNodeInsertion(evict);
return null;
}
咱们来慢慢分析：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]
这是第一次执行的时候，此时table还是null，可以看到，这里并不是在我们new HashMap就创建了内部数组的，而是采用了懒加载的方式，等到实际使用的时候，才会去创建。既然走到了resize扩容方法，我们先看一下resize扩容方法
resize 方法解析
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//null
int oldCap = (oldTab == null) ? 0 : oldTab.length;//0
int oldThr = threshold;//0
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){
// newCap = oldCap << 1 扩容机制，新的容量是旧容量的2倍，新的阈值也是旧的阈值的两倍
newThr = oldThr << 1;
}
} else if (oldThr > 0){
newCap = oldThr;//8
} else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//16 * 0.75 = 12
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//12
}
threshold = newThr;//24
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个Node类型的数组。
table = newTab;//复制给HashMap的table属性
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//遍历数组
Node<K,V> e;
if ((e = oldTab[j]) != null) {//数组的第j个位置不为null
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//重新分布位置
else if (e instanceof TreeNode)//已经是树型，重新分布，即断树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 保护顺序 [链表]
Node<K,V> loHead = null, loTail = null;//low
Node<K,V> hiHead = null, hiTail = null;//high
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//如果hash%oldCap = 0，则表示在低位上
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 否则将节点移动到新增的高位上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//将原来仅分布在低位的节点，拆分到对应的高位和低位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
首先我们看第一个判断：
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
} else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY){
// newCap = oldCap << 1 扩容机制，新的容量是旧容量的2倍，新的阈值也是旧的阈值的两倍
newThr = oldThr << 1;
}
}
在第一次是不成立，因为 int oldCap = (oldTab == null) ? 0 : oldTab.length;//0 是为0. 但是当我们第二次进行初始化的时候，就会走到这个判断，首先判断是不是大于最大容量static final int MAXIMUM_CAPACITY = 1 << 30; ,如果是，则将阈值赋为int类型的最大值,即 2的31次方减1. 否则，将新的容量扩容到原来的两倍。左移一位；
0001 0000 => 16
0010 0000 => 32 16经过左移一位，其实就是在右边补0.
(newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY 这个条件表示，新的容量需要小于最大容量，并且老容量要大于static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16.
即：如果我们第一次使用指定容量的构造方法来实例化对象的话，如果指定的是3，我们知道经过处理，初始化容量是4，此时的阈值是3. 但是下一次扩容时，可以发现当newCap变为8的时候，由于oldCap 不大于默认初始化容量16.则不会将阈值乘2. 即此时阈值还是3. 这样的目的是为了让table的容量更加快的扩容到16.
继续：
else if (oldThr > 0){
newCap = oldThr;//8
}
表示原来oldThr已经被初始化了，这种情况会出现在，指定了初始化容量的时候。如下：
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
//如果初始化容量大于最大容量，则仅初始化为最大容量。
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
可以看到，这里将处理后的初始化容量initialCapaciry赋值给了阈值threshold。而等到put值的时候，此时oldCap为0，但是oldThr大于0.所以会走到这句。
继续：
这里判断执行是，表示oldCap和oldThr的值都不大于0.所以会走到这里。
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//12
}
其实就是初始化时，选用的是无参数的构造方法，当第一次put值的时候就会执行到这。将newCap设置为默认初始化容量16. 然后通过默认初始化容量DEFAULT_INITIAL_CAPACITY和默认初始化负载因子DEFAULT_LOAD_FACTOR计算出newThr，新阈值。
继续：
下面这个判断需要成立的话，即表示前面都没有给这个newThr赋值。
if (newThr == 0) {
float ft = (float)newCap * loadFactor;//16 * 0.75 = 12
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);//12
}
存在于两处：
第一：
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
这个判断；但是这里直接返回了，不会走到后面，所以这个判断不是为这里准备的。还有一个地方：
第二：
else if (oldThr > 0){
newCap = oldThr;//8
}
就是这；当初始化时指定了初始化容量，表示oldThr已经复制了，并且newCap也有值了，但是没有计算出新的阈值newThr. 所以这里计算出新的阈值。
继续：
threshold = newThr;//24
将新计算出来的阈值，复制给当前对象的threshold属性。
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//创建一个Node类型的数组。
table = newTab;//复制给HashMap的table属性
上面这句就是关键的一句了。我们都知道HashMap底层的数据结构是数组+链表+红黑树。这就是创建数组的地方。创建一个长度为newCap，类型为Node的数组。然后将新创建的数组复制给当前对象的table属性。
继续：
下面就是在非第一次扩容（即初始化数组） 的时候需要进行的数组重新排布的过程。由于HashMap是通过数组做成一个一个的桶的，所以外层通过for循环来遍历数组。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//遍历数组
Node<K,V> e;
if ((e = oldTab[j]) != null) {//数组的第j个位置不为null
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//重新分布位置
else if (e instanceof TreeNode)//已经是树型，重新分布，即断树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order 保护顺序 [链表]
Node<K,V> loHead = null, loTail = null;//low
Node<K,V> hiHead = null, hiTail = null;//high
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//如果hash%oldCap = 0，则表示在低位上
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 否则将节点移动到新增的高位上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//将原来仅分布在低位的节点，拆分到对应的高位和低位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
当遇到为null的位置就跳过；
if ((e = oldTab[j]) != null) {//数组的第j个位置不为null
在重新分布位置的时候，存在三种情况：
- ① 同一个数组下标下，只存在一个元素，即没有发生hash碰撞
- ② 当前数组下标位置上是链表结构，即链表长度没有超过8，还没有形成红黑树
- ③ 当前数组下标位置上的结构是红黑树。
第一种：没有发生hash碰撞的
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;//重新分布位置
可以看到这里在重新计算位置。即使用当前节点的hash值与新的容量进行取模。【为什么不用%来取模，后面文章会有，其实就是为什么HashMap的初始化容量一定要是2的n次方】；
我们假设oldCap是16，即newCap是32. 并且假设e.hash为18。
原来的位置在：
0000 0000 0000 0000 0000 0001 0010
0000 0000 0000 0000 0000 0000 1111
----------------------------------
0000 0000 0000 0000 0000 0000 0020 =>即当数组容量是16的时候，hash值为18的元素在下标为2的位置。
新的位置：
0000 0000 0000 0000 0000 0001 0010
0000 0000 0000 0000 0000 0001 1111
----------------------------------
0000 0000 0000 0000 0000 0001 0010 => 即当数组容量扩容到32时，hash值都为18的元素因为放在下标为18的地方。
首先我们先不纠结为什么不是用%来取模，这里可以看到，其实就是重新计算hash值与容量的模。来获取到新的位置。
第二种：产生hash碰撞，此时已经是链表结构
else { // preserve order 保护顺序 [链表]
Node<K,V> loHead = null, loTail = null;//low
Node<K,V> hiHead = null, hiTail = null;//high
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//如果hash%oldCap = 0，则表示在低位上
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {// 否则将节点移动到新增的高位上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);//将原来仅分布在低位的节点，拆分到对应的高位和低位
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
这里由于已经形成了链表，需要重新分布位置，所以需要将原来的一条链拆分为两条链。do…while循环用于遍历链表。分别定义了loHead低位链和hiHead高位链，我们主要来看一下怎么将其区分是高位链的节点还是低位链的节点：
if ((e.hash & oldCap) == 0)
这个判断和上面的计算位置相似，但是可以看到，上面计算位置是-1.这里没有减一，即此时oldCap转为二进制其实就是最高位为1，其他为均为0，这样做与&运算，其实就是判断hash值与oldCap最高的1对应的位置是不是1. 如不是1，则计算结果为0，放置在低位链上，如果非0，则放置在高位链上。
0000 0000 0000 0000 0000 0000 0001 0010 =>18
0000 0000 0000 0000 0000 0000 0001 0000 =>16
--------------------------------------- => &
0000 0000 0000 0000 0000 0000 0001 0000 => 结果不为0，放置在高位上
通过上面的判断，我们知道如何进行链表拆分了。后面就是把低位链放置在原来对应的位置上，即table[index]，把高位链放置在table[index+oldCap]位置上。
第三种：链表的长度超过了8，已经形成了红黑树
else if (e instanceof TreeNode)//已经是树型，重新分布，即断树
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
通过判断，此时的节点已经是TreeNode类型的节点，所以已经是红黑树了，需要执行拆分方法split。
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
//虽然此时是树形，但是保持了原有链表的结构，依旧可以遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {// 同样判断是高位还是低位
//高低位重新组建新的链表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;//记录low位的节点数
} else {//低位
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;//记录high位的节点数
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)//如果小于等于6，则进行解树形化
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
//hiHead不为null，表示经过扩容以及重新分布，已经拆出一部分节点到对应的高位了，所以需要重新树形化。
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)//同样，如果拆过来的节点小于等于6个，需要解树形化[树->链表]
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)//同样，如果扩容以及重新分布之后，不是全部拆到了高位，则需要重新树形化。
hiHead.treeify(tab);
}
}
}
这个split方法又是不简单，声明已经说了，这里不讨论红黑树生成的过程，这样这个过程可能稍微简单一点。
//虽然此时是树形，但是保持了原有链表的结构，依旧可以遍历
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {// 同样判断是高位还是低位
//高低位重新组建新的链表
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;//记录low位的节点数
} else {//低位
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;//记录high位的节点数
}
}
这里跟前面的链表过程相似，因为TreeNode是Node节点的子类，同时除了维护parent,left,right三个属性外，还维护了prev，即TreeNode维护了一个双向链表【后面由链表转为红黑树的过程可以看到】。而链表是一个单向链表.
通过与前面相似的判断之后，形成了高位链表和低位链表，并且统计了相应的个数。
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)//如果小于等于6，则进行解树形化
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
//hiHead不为null，表示经过扩容以及重新分布，已经拆出一部分节点到对应的高位了，所以需要重新树形化。
loHead.treeify(tab);
}
}
从上面的判断得知，首先判断低位链是不是存在，即如果低位链上没有元素，那其实就是整个红黑树的搬移，不用进行处理低位链了。
- 如果非null, 并且此时低位链节点的个数小于等于【UNTREEIFY_THRESHOLD】6，需要执行解树形化，即将红黑树转为链表【单向】。并将链表放置在低位上table[index].
- 如果大于6个并且高位链不为null，即表示原来的一棵红黑树，现在需要拆分：拆分为低位红黑树，高位链表。或者是低位红黑树高位也是红黑树。并且此时由于一份为二，低位节点个数又大于6，需要重新调整红黑树的结构，执行树形化方法【treeify】
而高位和低位上相互对应的：
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)//同样，如果拆过来的节点小于等于6个，需要解树形化[树->链表]
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)//同样，如果扩容以及重新分布之后，不是全部拆到了高位，则需要重新树形化。
hiHead.treeify(tab);
}
}
如果高位的节点不为空并且节点个数小于等于6，则解树形化，并放置在高位。如果高位节点个数大于6并且低位存在元素，则重新执行treeify方法调整二叉树结构。至于如果实现树形化，此处不再讨论，详情请看文首声明。
至此，我们resize扩容方法就看得差不多了。我们回去putVal方法
回来才发现，看完这么多，putVal方法才走3行。唉 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-sTWGTIRj-1588582942177)(file:///C:\Users\ouYang\AppData\Local\Temp\SGPicFaceTpBq\13644\11170B79.png)]
继续：抛开扩容的方法
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//resize 扩容 [无参，第一次put，初始化为16]
if ((p = tab[i = (n - 1) & hash]) == null)
//创建一个节点，放置在tab的第i个位置上。
tab[i] = newNode(hash, key, value, null);
我们看第二个if判断，这里的(n - 1) & hash 与元素就不再赘述了，就是计算位置。即当前添加进来的key的hash值所计算得计算需要放置的位置上是否已经有元素了。如果为null，表示没有元素，直接创建一个Node节点放置在位置i上即可。
如果i位置上的元素不为null，即发生了hash碰撞，走else
else {//如果不为null，即表示当前数组位置上已经存在了值，发生了Hash冲突。
Node<K,V> e; K k;
//p就是冲突的第一个位置。hash值相同，key相同，或者equals。表示key相同。
//注意：相同的hash可能对应不同的key
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)//树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//链表[如果不是同一个元素，即hash冲突，但是key不同，并且此时不是树结构，则执行链表结构]
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD - 1 = 7 如果
//当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，链表存在的最长的串就是8个。
// 8个节点是一个临界值。
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;//同样，如果存在一样的key，则跳过
p = e;//相当于p=p.next
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
//如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
if (!onlyIfAbsent || oldValue == null)
e.value = value;//值覆盖
afterNodeAccess(e);
return oldValue;//返回oldValue
}
}
此时else里面的代码分为三个部分；
第一：位置i的元素的key的hash值与put进行的hash值是一样的，并且key也相等；即下面的条件为true。
p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))
可以判断此时put进来的key是已经存在的，是否覆盖后续再看。
第二：已经不是第一次碰撞了，已经形成了红黑树结构
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
已经是树的结构，需要执行putTreeVal方法。此时不做深究。
第三：已经是链表，还未形成树结构
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍历到最后一个节点。[采用尾插法]
p.next = newNode(hash, key, value, null);//将尾节点指向新创建的节点。
if (binCount >= TREEIFY_THRESHOLD - 1) // TREEIFY_THRESHOLD - 1 = 7 如果
//当链表添加到第9个时，就会触发树型化操作，即将链表转为红黑树。那这里其实可以知道，链表存在的最长的串就是8个。
// 8个节点是一个临界值。
treeifyBin(tab, hash);
break;
}
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;//同样，如果存在一样的key，则跳过
p = e;//相当于p=p.next
}
if条件if ((e = p.next) == null), 表示循环到最后一个节点，即采用尾插法，【同样，如果途中遇到相同的hash和key，则退出循环，后续处理】。当遍历到最后一个节点，此时链表长度是8，加上newNode，其实是添加第9个元素的时候，触发树形化的。当binCount大于等于7时，会将链表转为红黑树，即执行treeifyBin方法
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
首先判断tab是否为null，或者此时数组的长度是否大于最小树形化容量【MIN_TREEIFY_CAPACITY = 64;】。否则不会转为树，而是进行扩容。else表示满足条件。do…while循环做的事就是先将原来链表转为TreeNode类型的双向链表。
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
而replacementTreeNode方法就是将Node初始化为TreeNode:
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
通过下面的代码可以知道，这里就是在维护双向链表的前驱和后继。
p.prev = tl;
tl.next = p;
结束后就是想链表转为树，不做深究。
我们回来看：
if (e != null) { // existing mapping for key
V oldValue = e.value;
//onlyIfAbsent为false，或oldValue为null, 才会执行覆盖操作
//如果指定了onlyIfAbsent为true，则需要oldValue为null，才会进行值的覆盖，即才会存储。(putIfAbsent())
if (!onlyIfAbsent || oldValue == null)
e.value = value;//值覆盖
afterNodeAccess(e);
return oldValue;//返回oldValue
}
当我们在遍历的过程中，发现已经存在相同的key了，则需要通过判断来确地是否进行值的覆盖。
最后：
size+1. 并判断是否超过了阈值，否则就进行扩容。 afterNodeInsertion空方法。
++modCount;//并发操作，fast-fail
if (++size > threshold)//size+1
resize();
afterNodeInsertion(evict);
至此，putVal方法和resize方法就基本看完了
转载：https://blog.csdn.net/ooyhao/article/details/105919968