6

我试图找出 Java 中 HashMap 和 TreeMap 中 equals() 的计算复杂性。现在，您可能会说在这两种情况下它应该是相同的，因为 HashMap 和 TreeMap 都从 AbstractMap 继承了相同的实现。但是，在我完全接受之前，我需要一些解释。

这让我感到困惑。AbstractMap 文档中重写的 equals() 的部分解释是：

更正式地说，如果 m1.entrySet().equals(m2.entrySet())，则两个映射 m1 和 m2 表示相同的映射。

文档不清楚 entrySet 返回的集合是 HashSet 还是 SortedSet 或其他东西。在我看来，了解这一点很重要，因为它会影响整体分析。

如果 entrySet() 返回的集合是 HashSet 类型，那么可以在 O(n) 中比较两个集合 [两个哈希集合的相等成本]。但是，如果它们是 SortedSet 类型，那么它们可以在 O(nlogn) [在两个排序集的情况下相等的成本] 中进行比较。因此，在 HashMap 的情况下 equals() 的复杂性与在 SortedMap 的情况下不同，或者至少它应该基于我的推理。

我强烈怀疑我的推理在某个地方是错的，所以请随时告诉我我错在哪里。正确的推理是什么。最后，我对 HashMap 和 SortedMap 的 equals() 的复杂性感兴趣。谢谢。

4

1 回答 1

5

我相信你对这两种方法的复杂性是正确的。由于它们都继承了它们的 equals 实现AbstractMap，因此值得检查AbstractMap. 相关部分如下：

Map<K,V> m = (Map<K,V>) o;
if (m.size() != size())
    return false;

Iterator<Entry<K,V>> i = entrySet().iterator();
while (i.hasNext()) {
Entry<K,V> e = i.next();
K key = e.getKey();
V value = e.getValue();
if (value == null) {
    if (!(m.get(key)==null && m.containsKey(key)))
        return false;
} else {
    if (!value.equals(m.get(key)))
        return false;
}
return true;

请注意，它调用内部循环中的getand方法，这些方法被其子类覆盖。containsKey由于 HashMap 在 O(1) 中实现这些，而 TreeMap 在 O(log n) 中实现它们，这导致 Hashmap 的 O(n) 和 TreeMap 的 O(n log n) 的总体等于复杂度。

于 2013-09-17T05:57:37.617 回答