V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
amiwrong123
V2EX  ›  Java

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

  •  
  •   amiwrong123 · 2019-12-28 15:44:43 +08:00 · 2719 次点击
    这是一个创建于 1810 天前的主题,其中的信息可能已经有所发展或是发生改变。

    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);(这句肯定会被执行,当分不出大小时)的方向往下走,那岂不是也可能不对了吗?

    2 条回复    2020-11-12 16:00:27 +08:00
    Codelike
        1
    Codelike  
       2019-12-29 13:00:18 +08:00
    你所述想要删掉的代码的功能是,在无法比较出大小的情况下,进入到左右子树分别进行搜索。如果找到找到了相同的 key,就直接返回结果。和下面的 `dir = tieBreakOrder(k, pk);`不同的功能
    1194129822
        2
    1194129822  
       2020-11-12 16:00:27 +08:00
    tieBreakOrder 作用的是干什么的?根本不是比较元素大小的,而是和它名字一样是打破比较的。这个只在插入的时候用到(红黑树不同元素一定要比较大小)。就是说在这一步一定要插入了,因为 tieBreakOrder 已经不关心 a,b 顺序了[也无法保证]。因为严格执行比较 identityHashCode 也可能相同,那样根本分不出大小。所以搜索都没有用 tieBreakOrder,而是在左右子树都进行搜索。实际上可以认为 tieBreakOrder 其实没有什么作用,前面比较都无法通过,则直接令 a<b 就可以。
    可以看一下 Implementation notes. 有说明。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3805 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 05:28 · PVG 13:28 · LAX 21:28 · JFK 00:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.