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.