HashMap 和 SortedMap 中 equals() 的复杂性

Question

我试图找出 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() 的复杂性感兴趣。谢谢。

Answer 1

我相信您对这两种方法的复杂性的看法是正确的。由于它们都继承了 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;

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