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 表示获取数组中的位置
//p == null 表示p在当前数组中位置不存在，则直接存放到数组当前位置
tab[i] = newNode(hash, key, value, null);
else { //表示新元素在数组中存在
Node<K,V> e; K k;
//判断当前存入元素的k和数组中当前位置已经存在元素的k值是否相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p; //把当前数组中存在的元素赋值给e
else if (p instanceof TreeNode) //判断数组中当前位置元素是否为tree的类型
//把数据转变成树结构
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//以上条件都不满足，则以链表的形式存储
for (int binCount = 0; ; ++binCount) {
//如果e==null当前的p节点为链表的头节点
if ((e = p.next) == null) {
//直接把新数据插入到链表头结点后面
p.next = newNode(hash, key, value, null);
//TREEIFY_THRESHOLD=8；TREEIFY_THRESHOLD表示链表转成红黑树的判断条件
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//把数组中当前位置的链表结构转成红黑树
treeifyBin(tab, hash);
break;
}
//如果新插入的k值和链表中下个节点已经存在的k值相同，则e p.next并退出循环
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; //把链表下个节点赋值给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数组
//h hash值
// K key
// V value
Class<?> kc = null;
boolean searched = false; //标识是否被收索过
TreeNode<K,V> root = (parent != null) ? root() : this; // 找到root根节点
for (TreeNode<K,V> p = root;;) { //从根节点开始遍历循环
int dir, ph; K pk;
// 根据hash值 判断方向
if ((ph = p.hash) > h)
// 大于放左侧
dir = -1;
else if (ph < h)
// 小于放右侧
dir = 1;
// 如果key 相等 直接返回该节点的引用 外边的方法会对其value进行设置
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
/**
*下面的步骤主要就是当发生冲突 也就是hash相等的时候
* 检验是否有hash相同 并且equals相同的节点。
* 也就是检验该键是否存在与该树上
*/
//说明进入下面这个判断的条件是 hash相同 但是equal不同
// 没有实现Comparable<C>接口或者 实现该接口 并且 k与pk Comparable比较结果相同
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//在左右子树递归的寻找 是否有key的hash相同 并且equals相同的节点
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相等的 那就必须进行插入操作
//打破平衡的方法的 分出大小 结果 只有-1 1
dir = tieBreakOrder(k, pk);
}
//下列操作进行插入节点
//xp 保存当前节点
TreeNode<K,V> xp = p;
//找到要插入节点的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
//创建出一个新的节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
//小于父亲节点 新节点放左孩子位置
xp.left = x;
else
//大于父亲节点 放右孩子位置
xp.right = x;
//维护双链表关系
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
//将root移到table数组的i 位置的第一个节点
//插入操作过红黑树之后 重新调整平衡。
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
添加树形节点，与添加双链表节点个过程类似：
1、从root节点开始寻找 如果目标k.hash 小于 当前节点的 hash ,那么到左树寻找，大于那么从右树寻找。如果找到key相同并且equals相同的节点 p 那就直接返回。
2、如果hash相同 但是equal不同 进而通过Comparable接口，进行比较，如果比较的结果如果还是相等，则在左右子树递归的寻找是否有与要插入的key equals相同的元素。如果有那么直接return返回。
（也即是没实现Comparable接口，大小由hash判定。实现了，则由Comparable接口的比较方法判定）
3、如果遍历完所有的节点 并未找到equals相同的节点。那就需要插入该新节点。必须分出大小，所以通过执行tieBreakOrder方法，该方法的返回值是-1，1。如果是-1则插入到左边节点，1就插入到右边节点。
4、插入完成之后，需要重新移动root节点 到table数组的i位置的第一个节点上 并且需重新平衡红黑树。
