Complexity of equals() in HashMap and SortedMap

Question

I am trying to figure out the computational complexity of equals() in both HashMap and TreeMap in Java. Now, you might say it should be same in both cases as both HashMap and TreeMap inherit the same implementation from AbstractMap. However, I am in need of some explanation before I can fully accept that.

Here is what confuses me. Part of the explanation in overridden equals() in AbstractMap documentation is:

More formally, two maps m1 and m2 represent the same mappings if m1.entrySet().equals(m2.entrySet()).

The documentation is not clear on whether the sets returned by the entrySet are HashSet or SortedSet or something else. In my view this is important to know as it would impact the overall analysis.

If sets returned by entrySet() are of type HashSet then two sets can compared in O(n) [cost of equals in case of two hash sets]. However, if they are of type SortedSet then they can be compared in O(nlogn) [cost of equals in case of two sorted sets]. Consequently, complexity of equals() in case of HashMap would be different then in case of SortedMap, or at least it should be based on my reasoning.

I strongly suspect I am wrong somewhere in my reasoning, so feel free to tell me where I am wrong. What is the correct reasoning. And, finally I am interested in the complexity of equals() in case of HashMap and SortedMap. Thanks.

Bohannon

Answer 1

I believe you are right about the complexity of both methods. Since they both inherit their equals implementation from AbstractMap, it is worthwhile inspecting the source code for AbstractMap. The relevant portion is as follows:

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;

Note that it calls the get and containsKey methods within the inner loop which are overridden by their subclasses. Since HashMap implements these in O(1) while TreeMap implements them in O(log n), that leads to the overall equals complexity of O(n) for Hashmap and O(n log n) for TreeMap.

Schnurr

I have been staring at code in all three AbstractMap, TreeMap, HashMap, and I think my original thinking was not wrong after all. Although, it is true that both TreeMap and HashMap inherit the same implementation of equals, but it is really the containskey and get methods that eventually make the final difference. Both of them are overridden in the respective concrete map types. I seem to have overlooked this point in my earlier reasoning. Thanks @Schnurr – Bohannon