代码之家 › 专栏 › 技术社区 › yong _ta_Park

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

hashmap java

yong _ta_Park · 技术社区 · 2 年前

我一直在学习Java的HashMap,并提出了一些问题。正在查看 find 的方法 HashMap ,内容如下:

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

相比之下,中的其他方法 哈希图 例如 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;
}

在我看来,两者在遍历树节点方面都有共同点—— 发现 方法直接遍历树的节点,而 tieBreakOrder 似乎在比较几个值。

所以,我从原子操作的角度来思考它。我假设访问单个节点和比较原始数据值所花费的操作时间大致相同。因此,我得出的结论是 发现 实际遍历节点的方法可能比 tieBreakOrder ,它比较了许多原始值。

然而,我不确定我的假设是否正确,或者是否有任何其他原因可以让我更多地了解 发现 和 tieBreakOrder 方法?

0 回复 | 直到 2 年前

Thomas 2 年前

扩展我的评论:如果你阅读代码中的评论,你会看到 tieBrakOrder() :

当hashCodes相等且不可比较时,用于排序插入的平局打破实用程序。我们不需要总顺序,只需要一个一致的插入规则来保持重新平衡的等价性。超过必要程度的打结会稍微简化测试。

这意味着在构建树时,需要打破平局以保持一致的秩序,这种情况发生在 putTreeVal() 或 treeify() .

另一方面 find() 只使用树中已经存在的顺序,如果你查看该方法,你会看到其他几件事首先被尝试:

如果节点的哈希代码小于或大于我们要查找的哈希代码,请向左或向右
如果散列码相等,并且密钥也匹配,我们就找到了正确的节点
如果散列码相等,但密钥不匹配,则情况与 treeify() 等等:我们需要另一种方法来找到正确的节点
- 首先,该方法检查我们是否在最外面的节点之一,并向内部发送搜索
- 如果我们不在最外面的节点之一,则通过比较关键字来确定搜索方向,如果它们是可比较的
- 如果关键字不可比较,则搜索首先指向右侧,如果在那里没有找到任何内容,则继续向左搜索(这是您共享的片段)

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

编辑 :使用不是很有意义吗 tieBreakOrder() 在里面 发现 以确定是向左看还是向右看?(来自评论)

不,这不起作用,因为平局打破使用每个密钥的身份哈希代码来确定顺序,并且该代码看起来是“随机的”(即,同一类的两个相等实例可以具有完全不同的身份哈希码)。

让我们举一个例子:为了简单起见,让我们假设以下键类:

class Version {
  String value;

  public boolean equals(Object other) {
    // compare values
  }

  public int hashCode() {  
    // For the sake of simplicity we either return 0 or 1.
    // In reality you'd use a proper algorithm that is unlikely to
    // produce the same hash code for different values albeit it 
    // still could happen
    return value.hashCode() % 2;
  }
}

如您所见,如果我们现在有一个使用 Version 作为一个密钥,它可能需要采用平局打破,因为这些实例可能具有相同的哈希代码,不能保证相等,也不具有可比性。

让我们假设我们使用以下密钥,这些密钥恰好具有相同的哈希代码(用于参数的假设):

new Version("1.0") ,身份哈希代码:1234
new Version("2.0") ,身份哈希码:999
new Version("3.0") ,身份哈希码:1024

平局打破现在会命令他们 "2.0", "3.0", "1.0" .

现在假设您正在查找带有密钥的条目 Version("1.0") 。如果您命中包含的节点 "3.0" ,你是向左搜索还是向右搜索?

如果你认为“是的,因为密钥的身份哈希代码是1234”,那么想想看:你可能不知道密钥的确切实例,所以你生成了一个新的实例- map.get(new Version("1.0")) -你会期望这能奏效的。

然而,这个新实例得到了身份哈希代码1001——如果你点击 "3.0" 进入