已经有了 tieBreakOrder，为啥 HashMap 的 putTreeVal 里还是要左右子树都要去找一遍？

[amiwrong123]

jdk1.8

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)
            dir = -1;
        else if (ph < h)
            dir = 1;
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //这个分支我觉得可以替换为下面的代码
        //如果使用 comparable 接口还是比较不出大小，那么进入分支
        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            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;
            }
            dir = tieBreakOrder(k, pk);
        }

        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;
            moveRootToFront(tab, balanceInsertion(root, x));
            return null;
        }
    }
}

我觉得上面这个分支可以替换为下面的代码

        else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                 (dir = compareComparables(kc, k, pk)) == 0) {
            dir = tieBreakOrder(k, pk);
        }

因为 tieBreakOrder 就是当实在比较不出大小时，用来给一种默认的顺序（默认的顺序是新插入的节点更小，可以从调用 tieBreakOrder 的实参顺序 tieBreakOrder(k, pk)看出来，treeify 函数里也是这个实参顺序）。那既然，即使分不出大小也有默认顺序，那么就按照顺序走二叉查找的过程不就得了，把判断相等的任务全权交给else if ((pk = p.key) == k || (k != null && k.equals(pk)))不就好了吗？

emmmmm。。。我写到这里好像想到答案了，，，难道是因为还有那些左旋右旋操作，所以这种默认顺序可能被破坏呗。但这好像也不对，那既然默认顺序会被破坏，那么你现在按照dir = tieBreakOrder(k, pk);（这句肯定会被执行，当分不出大小时）的方向往下走，那岂不是也可能不对了吗？

[Codelike]

你所述想要删掉的代码的功能是，在无法比较出大小的情况下，进入到左右子树分别进行搜索。如果找到找到了相同的 key，就直接返回结果。和下面的 `dir = tieBreakOrder(k, pk);`不同的功能

[1194129822]

tieBreakOrder 作用的是干什么的？根本不是比较元素大小的，而是和它名字一样是打破比较的。这个只在插入的时候用到(红黑树不同元素一定要比较大小)。就是说在这一步一定要插入了，因为 tieBreakOrder 已经不关心 a,b 顺序了[也无法保证]。因为严格执行比较 identityHashCode 也可能相同，那样根本分不出大小。所以搜索都没有用 tieBreakOrder，而是在左右子树都进行搜索。实际上可以认为 tieBreakOrder 其实没有什么作用，前面比较都无法通过，则直接令 a<b 就可以。
可以看一下 Implementation notes. 有说明。