final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;//k的类型
boolean searched = false;//是否遍历过树了
TreeNode<K,V> root = (parent != null) ? root() : this;//树的根节点
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;//dir树的左右方向，ph当前节点的hash，pk当前节点的key值
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
//根据当前节点key值、hash和传进来要插入的key值、hash一般都能得到一个左或右方向
//或者当前节点key值、hash和传进来要插入的key值、hash相等或equals
//但是还有一种情况就是hash相等key不equals
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
//走到这里说明：指定key没有实现comparable接口
//或者实现了comparable接口并且和当前节点的键对象比较之后相等
/**searched 标识是否已经对比过当前节点的左右子节点了
* 如果还没有遍历过，那么就递归遍历对比，看是否能够得到那个键对象equals相等的节点
* 如果得到了键的equals相等的的节点就返回
* 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了
* find(h, k, kc)递归、while遍历ch的所有节点直到找到与k 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相等的节点
dir = tieBreakOrder(k, pk);//把两个key的object的hashcode()方法生成的hashcode比较决定方向
}
TreeNode<K,V> xp = p; // 定义xp指向当前节点
/*
* 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
* 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
* 如果以上两条当中有一个子节点不为空，这个if中还做了一件事，那就是把p已经指向了对应的不为空的子节点，开始下一轮的比较
*/
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 如果恰好要添加的方向上的子节点为空，此时节点p已经指向了这个空的子节点
Node<K,V> xpn = xp.next; // 获取当前节点的next节点
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); // 创建一个新的树节点
if (dir <= 0)
xp.left = x; // 左孩子指向到这个新的树节点
else
xp.right = x; // 右孩子指向到这个新的树节点
xp.next = x; // 链表中的next节点指向到这个新的树节点
x.parent = x.prev = xp; // 这个新的树节点的父节点、前节点均设置为 当前的树节点
if (xpn != null) // 如果原来的next节点不为空
((TreeNode<K,V>)xpn).prev = x; // 那么原来的next节点的前节点指向到新的树节点
moveRootToFront(tab, balanceInsertion(root, x));// 重新平衡，以及新的根节点置顶
return null; // 返回空，意味着产生了一个新节点
}
}
}