putVal=>resize=>返回
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
/* 第13次插入值(是put的第13次 不代表13桶都有了值后再扩容) 讨论扩容 下面用②走标识13次 */
Node<K, V>[] tab;/* ②走：16 */
Node<K, V> p;/* ②走：空 */ // p代表的就是桶的位置每次都会为空
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;// 若当前哈希数组table的长度为0，则进行扩容
if ((p = tab[i = (n - 1) & hash]) == null)// 确定输入的hash在哈希数组中对应的下标i
// 若数组该位置之前没有被占用，则新建一个节点放入，插入完成。
/* ②走：空 看情况走不变 */
tab[i] = newNode(hash, key, value, null);
else {// 桶内已经有元素情况
Node<K, V> e;
K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;// 放入元素和头元素相同,进行替换
else if (p instanceof TreeNode)// 不相同,则判断是否为TreeNode
/**
* 若该位置的第一个节点p为TreeNode类型，说明这里存放的是一棵红黑树，p为根节点。
* 于是交给putTreeVal方法来完成后续操作，该方法下文会有详述
**/
e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
// 走到这里，说明p不匹配且是一个链表的头结点，该遍历链表了
// 链表的情况,这里是先进行循环,在循环的过程中判断出元素超过TREEIFY_THRESHOLD则进行treeifyBin操作
for (int binCount = 0;; ++binCount) {
/** e指向p的下一个节点 **/
if ((e = p.next) == null) {
// 当next是null的时候就是尾部了,这里就是把新放入的元素加到链表尾部的操作
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// treeifyBin操作 转换成tree结构
/**
* 若插入后，该桶中的节点个数已达到了树化阈值
* 则对该桶进行树化。该部分源码下文会有详述
**/
treeifyBin(tab, hash);
break;
}
// 这里判断已经有相同key的元素
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
/**
* 匹配成功，我们需要用新的value来覆盖e节点
**/
break;
p = e; // 循环继续
}
}
// 若执行到此时e不为空，则说明在map中找到了与key相匹配的节点e
if (e != null) { // existing mapping for key
V oldValue = e.value;// 暂存e节点当前的值为oldValue
// 这里处理onlyIfAbsent,先新建一个node,然后再判断onlyIfAbsent,来决定是否替换原来的元素.
// 注意如果原来的元素的value是会替换掉的!
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 钩子方法 LinkedHashMap使用
afterNodeAccess(e);
return oldValue;
}
}
/**** --执行到此处说明没有匹配到已存在节点，一定是有新节点插入-- ****/
++modCount; // 结构操作数加一
// 触发resize
if (++size > threshold)
/* ②走：去扩容 */
resize();// 插入后，map中的节点数加一，若此时已达阈值，则扩容
afterNodeInsertion(evict);// 同样的钩子方法，通知子类有新节点插入
return null;// 同样的钩子方法，通知子类有新节点插入
}
final Node<K, V>[] resize() {
/* ②走： */
Node<K, V>[] oldTab = table;/* ②走：oldTab = 16 */
int oldCap = (oldTab == null) ? 0 : oldTab.length;/* ②走：oldCap = 16 */
int oldThr = threshold;/* ②走：oldThr = 12 */// map在第一次put值时会初始化化为12
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) {// 已第一次（put）举例oldCap << 1 意思：0001左移 0010 ； 就是1=>2
/* ②走：oldThr = 12 ;newCap=32 */ // 就是2任然小于2^30 且 大于2^4（如下）
// 1000=>1 0000: 8=> 16 (塞了16个值正好满足)
newThr = oldThr << 1;/* ②走：newThr = 24 */ // newThr为32
}
} else if (oldThr > 0) { // initial capacity was placed in threshold
newCap = oldThr;
} else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float) newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
}
/* ②走：threshold = 24 */
threshold = newThr;// 32
@SuppressWarnings({ "rawtypes", "unchecked" })
Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {/* ②走：oldCap = 16 */
Node<K, V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;/* ②走：oldTab[j]置空 */
if (e.next == null)/* ②走：判断是不是链表结构 ;newCap=32 */
newTab[e.hash & (newCap - 1)] = e;/* ②走：对应的位置存值 */
else if (e instanceof TreeNode)/* ②走：判断是不是链表树结构 */
((TreeNode<K, V>) e).split(this, newTab, j, oldCap);
else { // preserve order
/* ②走：判断是链表结构 */
/**
* 把原有链表拆成两个链表（优化索引）
* 链表1存放在低位（原索引位置）
* 想这样的：
* oldCap=16=>1 0000
* map.put(241, "1");高 1111 0001
* map.put(113, "1");高 111 0001
* map.put(17, "1");高 11 0001
* map.put(49, "1");高 1 0001
* ***
* map.put(1, "1");低 0001
*/
Node<K, V> loHead = null, loTail = null;//
Node<K, V> hiHead = null, hiTail = null;
Node<K, V> next;
do {
/**
* 每次循环的时候只会确定高位低位，所以 loHead和loTail/hiHead和hiTail 的内存地址是一致的
* 而循环的时候e的结构不断变化，所以将loTail或hiTail的next的改变等于loHead和hiHead在实时
* 变化；最后赋值的时候置是处理掉未经筛选的值
*/
next = e.next;/* ②走：next=> (hash键：值) */
if ((e.hash & oldCap) == 0) {/* ②走：oldCap = 16 */
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
} else {
if (hiTail == null)
/* ②走 1、：链表结构第一次替换 hiHead=e 后基本 一步拿到了所有的值 */
hiHead = e;
else
hiTail.next = e;
/* ②走 1、：链表结构第一次替换 hiTail=链表第一个 */
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;
}
