关于Java的HashMap`find`方法和`tieBreakOrder`比较的问题

Question

我一直在研究Java的HashMap，出现了一些问题。 再看

find

的

HashMap

方法，写法如下：

else if ((q = pr.find(h, k, kc)) != null)
                return q;
            else
                p = pl;

相比之下，

HashMap

中的其他方法（例如

putTreeVal

或

treeify

）使用

tieBreakOrder

方法。我很好奇这两者之间的区别。

static int tieBreakOrder(Object a, Object b) {
        int d;
        if (a == null || b == null ||
            (d = a.getClass().getName().
             compareTo(b.getClass().getName())) == 0)
            d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                 -1 : 1);
        return d;
    }

在我看来，两者在遍历树节点方面都有共性——

find

方法直接遍历树的节点，而

tieBreakOrder

似乎是在比较几个值。

所以，我是从原子操作的角度来思考的。我假设访问单个节点并比较原始数据值大约需要相同的操作时间。因此，我得出的结论是，实际上遍历节点的

find

方法可能比比较许多原始值的

tieBreakOrder

更快。

但是，我不确定我的假设是否正确，或者是否有其他原因让我可以更多地了解

find

和

tieBreakOrder

方法之间的区别？

非常感谢您帮助回答这个问题。谢谢！

Answer 1

扩展我的评论：如果你阅读代码中的评论，你会看到这个

tieBrakOrder()

:

打破平局实用程序，用于在 hashCode 相等且不可比较时对插入进行排序。我们不需要全序，只需要一致的插入规则来维持重新平衡之间的等效性。超出必要范围的平局打破会稍微简化测试。

这意味着在

putTreeVal()

或

treeify()

期间构建树时，需要打破平局以保持一致的顺序。

另一方面，

find()

仅使用树中已有的顺序，如果您查看该方法，您会看到首先尝试的其他一些操作：

• 如果节点的哈希码小于或大于我们要查找的哈希码，则向左或向右移动
• 如果哈希码相等并且密钥也匹配，我们就找到了正确的节点
• 如果哈希码相等但密钥不匹配，我们会遇到与

  treeify()

  等类似的情况：我们需要另一种方法来找到正确的节点
  • 首先，该方法检查我们是否位于最外层节点之一并向内发送搜索
  • 如果我们不在最外层节点之一，则通过比较键（如果它们具有可比性）来确定搜索方向
  • 如果键不具有可比性，搜索将首先定向到右侧，如果没有找到任何内容，则继续向左搜索（这是您共享的片段）

正如你所看到的，这个逻辑中没有必要打破平局。搜索以确定性方式完成，即使重建树也会返回相同的结果 - 这就是打破平局所确保的。