说明看注释
一、putTreeVal方法
final TreeNode<K, V> putTreeVal(HashMap<K, V> map, Node<K, V>[] tab, int h, K k, V v) {
//kc key的class
Class<?> kc = null;
//已搜索
boolean searched = false;
//获得根节点
TreeNode<K, V> root = (parent != null) ? root() : this;
//从根节点开始遍历
for (TreeNode<K, V> p = root; ; ) {
//p 当前循环的节点
//ph p的哈希值，pk p的key
int dir, ph = p.hash;
K pk = p.key;
//比较哈希值大小，判断要插入的位置
if (ph > h) {
dir = -1;
} else if (ph < h) {
dir = 1;
//如果key相等
} else if (Objects.equals(k, pk)) {
//直接返回p
return p;
//如果哈希值相等但是key不相等
} else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) {
//key不是可比较可类，或者pk与key比较后相等
//当还未进入过此次判断时，进行这次判断（只能进入一次）
if (!searched) {
//ch p节点的左右子节点，q 为ch节点通过h，k，kc从其子节点中找到的节点
TreeNode<K, V> q, ch;
//将searched设置为true防止下次进入
searched = true;
//将p节点下的左右子树遍历一遍
//如果ch节点不为空，q节点不为空，说明找到了
if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) {
//返回q节点
return q;
}
}
//这里表示ch节点为空或者q节点为空，使用tieBreakOrder方法进行比较
dir = tieBreakOrder(k, pk);
}
//到此处说明没有找到节点，当前是插入操作
//将xp节点指向q节点
TreeNode<K, V> xp = p;
//根据dir的值，获取p的左节点或者右节点,并由p节点指向
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//当当前要插入的节点为null时才可到此处
//注：TreeNode不仅维护了节点红黑树关系还维护了链表关系
//获得当前节点的后节点xpn（可以为null）
Node<K, V> xpn = xp.next;
//用传入的h，k，v生成一个新的TreeNode，并且将xpn节点插入其尾部
TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
//根据dir的值放入相应的位置
if (dir <= 0) {
xp.left = x;
} else {
xp.right = x;
}
//再将x节点设置为xp节点的后节点
//每个插入到红黑的节点也会插入到链表尾部
xp.next = x;
//将xp节点设置为x节点的前节点和父节点
x.parent = x.prev = xp;
if (xpn != null) {
//当xpn不为null时，将x节点设置为xpn节点的前节点
((TreeNode<K, V>) xpn).prev = x;
}
//平衡红黑树，并保证平衡后的根节点放到数组中
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
二、balanceInsertion方法
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root, TreeNode<K, V> x) {
//x 当前添加的节点
//root 根节点
//设置x节点为红色（红黑树当前节点默认为红色）
//如果设置为黑色必定会违反红黑数特性5
x.red = true;
//xp x节点的父节点
//xpp xp节点的父节点
//xppl xpp节点的左节点
//xppr xpp节点的右节点
for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
//若插入的是根节点，设置为黑色直接返回
//满足红黑树特性2
if ((xp = x.parent) == null) {
x.red = false;
return x;
//xp节点为黑色不会影响红黑数的结构直接返回根节点
//xpp节点为空说明xp节点为根节点，直接返回跟节点
} else if (!xp.red || (xpp = xp.parent) == null) {
return root;
}
//如果xp节点等于xppl节点
if (xp == (xppl = xpp.left)) {
//xppr节点不为空且xppr节点是红色的
if ((xppr = xpp.right) != null && xppr.red) {
//将xppr节点和xp节点设置为黑色
xppr.red = false;
xp.red = false;
//将xpp节点设置为红色
xpp.red = true;
//将x节点的指针指向xpp节点
//此处是因为xpp节点向下已经没有问题了，但xpp节点之上肯会有问题
//指向xpp节点是为了检查xpp节点之上的节点
x = xpp;
} else {
//xppr节点为空或xppr节点为黑色
if (x == xp.right) {
//如果x节点是xp节点的右节点
//进行左旋操作，将x节点替换为xp节点
root = rotateLeft(root, x = xp);
//给xpp节点赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果xp节点不为空
if (xp != null) {
//xp节点变为黑色
xp.red = false;
//如果xpp节点不为空
if (xpp != null) {
//xpp节点变为红色
xpp.red = true;
//进行右旋操作
root = rotateRight(root, xpp);
}
}
}
//如果xp节点为xpp节点的右节点
} else {
//如果xppl节点不为空且xppl节点是红色的
if (xppl != null && xppl.red) {
//将xppl节点和xp节点修改为黑色
xppl.red = false;
xp.red = false;
//xpp节点修改为红色
xpp.red = true;
//将x节点的指针指向xpp节点
//此处是因为xpp节点向下已经没有问题了，但xpp节点之上肯会有问题
//指向xpp节点是为了检查xpp节点之上的节点
x = xpp;
} else {
//如果xppl节点为空或者xppl节点为黑色
//如果x节点是xp节点的左节点
if (x == xp.left) {
//进行右旋操作，将x节点替换为xp节点
root = rotateRight(root, x = xp);
//给xpp节点赋值
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果xp节点不为空
if (xp != null) {
//将xp节点设置为黑色
xp.red = false;
//如果xpp节点不为空
if (xpp != null) {
//将xpp节点设置为红色的
xpp.red = true;
//进行左旋操作
root = rotateLeft(root, xpp);
}
}
}
}
}
}
三、rotateLeft和rotateRight
static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root, TreeNode<K, V> p) {
//r p节点的右节点
//pp p节点的父节点
//rl r节点的左节点
TreeNode<K, V> r, pp, rl;
//p节点不为空，且r节点不为空
if (p != null && (r = p.right) != null) {
//rl节点变为p节点的右节点，如果rl节点不为空，则p节点变为rl的父节点
if ((rl = p.right = r.left) != null) {
rl.parent = p;
}
//pp节点变为r节点的父节点，若pp节点为空，则r节点成为根节点
if ((pp = r.parent = p.parent) == null) {
(root = r).red = false;
//若pp节点不为空，则判断p节点在pp节点的那一边，把r节点放在相应位置上
} else if (pp.left == p) {
pp.left = r;
} else {
pp.right = r;
}
//p节点变成r节点的左节点
r.left = p;
//r节点变成p节点的父节点
p.parent = r;
}
return root;
}
static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root, TreeNode<K, V> p) {
//l p节点的左节点
//pp p节点的父节点
//lr l节点的右节点
TreeNode<K, V> l, pp, lr;
//p节点不为空，l节点不为空
if (p != null && (l = p.left) != null) {
//lr节点变为p节点的左节点,如果lr节点不为空，则p节点变为lr节点的父节点
if ((lr = p.left = l.right) != null) {
lr.parent = p;
}
//pp节点变为l的父节点，如果pp节点为空，则l节点变为跟节点
if ((pp = l.parent = p.parent) == null) {
(root = l).red = false;
//如果pp节点不为空，则判断p节点在pp节点的那一边，把l节点放入对应的位置
} else if (pp.right == p) {
pp.right = l;
} else {
pp.left = l;
}
//p节点变为l节点的右节点
l.right = p;
//l节点变为p节点的父节点
p.parent = l;
}
return root;
}