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)
//進行table擴容
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) //(n - 1) & hash 表示獲取數(shù)組中的位置
//p == null 表示p在當前數(shù)組中位置不存在，則直接存放到數(shù)組當前位置
tab[i] = newNode(hash, key, value, null);
else { //表示新元素在數(shù)組中存在
Node<K,V> e; K k;
//判斷當前存入元素的k和數(shù)組中當前位置已經(jīng)存在元素的k值是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //把當前數(shù)組中存在的元素賦值給e
else if (p instanceof TreeNode) //判斷數(shù)組中當前位置元素是否為tree的類型
//把數(shù)據(jù)轉(zhuǎn)變成樹結(jié)構(gòu)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//以上條件都不滿足，則以鏈表的形式存儲
for (int binCount = 0; ; ++binCount) {
//如果e==null當前的p節(jié)點為鏈表的頭節(jié)點
if ((e = p.next) == null) {
//直接把新數(shù)據(jù)插入到鏈表頭結(jié)點后面
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD=8；TREEIFY_THRESHOLD表示鏈表轉(zhuǎn)成紅黑樹的判斷條件
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//把數(shù)組中當前位置的鏈表結(jié)構(gòu)轉(zhuǎn)成紅黑樹
treeifyBin(tab, hash);
break;
}
//如果新插入的k值和鏈表中下個節(jié)點已經(jīng)存在的k值相同，則e p.next并退出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //把鏈表下個節(jié)點賦值給p
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
// map 當前Hashmap對象
//tab Hashmap對象中的table數(shù)組
//h hash值
// K key
// V value
Class<?> kc = null;
boolean searched = false; //標識是否被收索過
TreeNode<K,V> root = (parent != null) ? root() : this; // 找到root根節(jié)點
for (TreeNode<K,V> p = root;;) { //從根節(jié)點開始遍歷循環(huán)
int dir, ph; K pk;
// 根據(jù)hash值 判斷方向
if ((ph = p.hash) > h)
// 大于放左側(cè)
dir = -1;
else if (ph < h)
// 小于放右側(cè)
dir = 1;
// 如果key 相等 直接返回該節(jié)點的引用 外邊的方法會對其value進行設(shè)置
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
/**
*下面的步驟主要就是當發(fā)生沖突 也就是hash相等的時候
* 檢驗是否有hash相同 并且equals相同的節(jié)點。
* 也就是檢驗該鍵是否存在與該樹上
*/
//說明進入下面這個判斷的條件是 hash相同 但是equal不同
// 沒有實現(xiàn)Comparable<C>接口或者 實現(xiàn)該接口 并且 k與pk Comparable比較結(jié)果相同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在左右子樹遞歸的尋找 是否有key的hash相同 并且equals相同的節(jié)點
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
//找到了 就直接返回
return q;
}
//說明紅黑樹中沒有與之equals相等的 那就必須進行插入操作
//打破平衡的方法的 分出大小 結(jié)果 只有-1 1
dir = tieBreakOrder(k, pk);
}
//下列操作進行插入節(jié)點
//xp 保存當前節(jié)點
TreeNode<K,V> xp = p;
//找到要插入節(jié)點的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//創(chuàng)建出一個新的節(jié)點
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
//小于父親節(jié)點 新節(jié)點放左孩子位置
xp.left = x;
else
//大于父親節(jié)點 放右孩子位置
xp.right = x;
//維護雙鏈表關(guān)系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//將root移到table數(shù)組的i 位置的第一個節(jié)點
//插入操作過紅黑樹之后 重新調(diào)整平衡。
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
添加樹形節(jié)點，與添加雙鏈表節(jié)點個過程類似：
1、從root節(jié)點開始尋找 如果目標k.hash 小于 當前節(jié)點的 hash ,那么到左樹尋找，大于那么從右樹尋找。如果找到key相同并且equals相同的節(jié)點 p 那就直接返回。
2、如果hash相同 但是equal不同 進而通過Comparable接口，進行比較，如果比較的結(jié)果如果還是相等，則在左右子樹遞歸的尋找是否有與要插入的key equals相同的元素。如果有那么直接return返回。
（也即是沒實現(xiàn)Comparable接口，大小由hash判定。實現(xiàn)了，則由Comparable接口的比較方法判定）
3、如果遍歷完所有的節(jié)點 并未找到equals相同的節(jié)點。那就需要插入該新節(jié)點。必須分出大小，所以通過執(zhí)行tieBreakOrder方法，該方法的返回值是-1，1。如果是-1則插入到左邊節(jié)點，1就插入到右邊節(jié)點。
4、插入完成之后，需要重新移動root節(jié)點 到table數(shù)組的i位置的第一個節(jié)點上 并且需重新平衡紅黑樹。
