PS:由于文档是我在本地编写好之后再复制过来的，有些文本格式没能完整的体现，故提供下述图片，供大家阅览，以便有更好的阅读体验：
HashMap之往红黑树添加元素-putTreeVal方法源码解读
1、当要put的元素所在数组索引位置已存在元素，且是红黑树类型时，就会调用putTreeVal方法添加元素到红黑树上，具体操作步骤如下：
- 从根节点开始，到左右子树，层层递进，遍历红黑树，找到用于存放元素的合适位置;
- 将元素放入指定位置，并修改链表/红黑树相关节点的前prev后next父parent子(left/right)指向；
- 平衡红黑树；
- 保证红黑树根节点是链表头节点
2、具体，详见下述的源码解析：
1、/HashMap中调用putTreeVal ()方法的地方/
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;
if ((p = tab[i = (n - 1) & hash]) == null)
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)
**e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);**
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
**if (e != null) {
// existing mapping for key，会与putTreeVal方法对应
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}**
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
2、/*HashMap的putTreeVal ()方法/
/*** Tree version of putVal. */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root; ; ) {
//从根节点开始遍历
int dir, ph; K pk;
if ((ph = p.hash) > h) //h小于p,hash，dir=-1<0
dir = -1;
else if (ph < h) //h大于p.hash,dir=1>0
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) //走到此处说明要put的元素的k的hash和k都跟p的hash和p的k相等，说明该关键字对应元素已经在map中存在过，位置就是p的位置，直接返回该元素，进入到putVal方法的// existing mapping for key处进行处理(将元素对应的旧值替换成要put的新值v)
return p;
//走到此处，说明：hash相等，k不等，需要继续确定位置(到左右子树中去寻找)
else if ((kc == null && (kc = comparableClassFor(k)) == null) || //k是不可比较类型
(dir = compareComparables(kc, k, pk)) == 0) {
//k和pk无法比较，或者可以比较但比较后为0相等(这里相等但是k本身又不相等,逻辑上讲不通，说明也还是没法比较；只能再去左右分支找一下看有没有相等k的元素)
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; //找到相同k的元素则返回
}
dir = tieBreakOrder(k, pk); //找不到说明没有相同k的元素，则直接用k和ok调用System. identityHashCode(Object x)进行终极PK
}
//疑问：为何最后一个else if里只判断不可比较的情况(还包含可比较但比较后为0,逻辑上讲不通的情况)，可比较的情况为什么不判断了呢？
(猜测(不一定准确，欢迎指正)：若k和pk可比较(结合上下文理解，这里可比较隐含的意思其实是两者肯定不等)，则根据两者计算得到的hash值h和ph应该可以判断出大小，就不需要走到最后一个else if里了。相当于前面已经处理过可比较的情况了，包含了可比较的情形。)
//截至到现在。经过上述处理，肯定可以确定dir的值了
TreeNode<K,V> xp = p; //这里将p原有的值存入xp，以备后续代码使用
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//判断dir所指向的方向上的左右分支是否有元素，若没有，则将新元素放到指定分支(确定了新元素要存放的位置在p之后)；若有元素，则继续往指定分支上循环递进处理下去
Node<K,V> xpn = xp.next; //因新元素位置在p之后,故要将x放入xp和xpn中间
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); //定义新元素，为xp=p的下一个next节点
if (dir <= 0) //小于等于0左节点
xp.left = x;
else//大于0右节点
xp.right = x;
xp.next = x; //x是xp的next节点
x.parent = x.prev = xp; //xp是x的parent父节点和prev前一个节点
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x; //将x放在xpn的前一个节点
moveRootToFront(tab, balanceInsertion(root, x)); //确保插入x后红黑树自平衡以及确保根节点是头节点
return null; //返回null，说明是新加入的k对应的元素
}
}
}
