3

What is the time complexity of Map.containsKey and Map.containsValue in Dart? I'd like to know for the following implementations:

  • LinkedHashMap
  • HashMap
  • SplayTreeMap

I assume for the hash map implementations containsKey is amortized constant time and containsValue is probably linear time. For SplayTreeMap, containsKey is probably logarithmic time while containsValue is probably still linear time. However, the documentation seems to be silent on the issue. The best I could find was for LinkedHashMap, which says:

An insertion-ordered [Map] with expected constant-time lookup.

This doesn't specify if you are looking up the key or the value, but presumably this is referring to the key.

The docs for Set (if you navigate to the implementations), on the other hand, are not silent. They give the time complexity.

I assume this is an oversight in the documentation, but perhaps they are silent because there is no guaranteed time complexity. (That's would be strange, though, because it goes against developer expectations.)

Suragch
  • 484,302
  • 314
  • 1,365
  • 1,393

1 Answers1

4

For containsKey, it's the same time as doing a lookup.

  • HashMap and LinkedHashMap: Expected constant time, worst-case linear time for degenerate hashCodes.
  • SplayTreeMap, ammortized logarithmic time.

For containsValue, it's linear in the number of elements (at least). It simply does the equivalent of map.values.contains(...). There is no efficient way to find a single value in a map, so there is no better way than looking through all of them in some order. Some potential HashMap implementations can be extra expensive because they traverse the entire backing store, and if the map had been grown big first, then had a lot of elements removed, then it might have a backing store which is significantly larger than its number of elements. Other implementations auto-shrink, or keep elements in a contiguous area, and won't have that problem. Very implementation dependent. No promises which implementation Dart uses.

lrn
  • 64,680
  • 7
  • 105
  • 121
  • Regarding sets, the [docs](https://api.dart.dev/stable/2.16.1/dart-collection/HashSet-class.html) say: "Most simple operations on `HashSet` are done in (potentially amortized) constant time". Would `HashSet` and `LinkedHashSet` also have worst-case linear time for degenerate `hashCode`s? – Suragch May 05 '22 at 07:40
  • 1
    Yes. If all the objects have the same hash code, then the hash code won't help you do the lookup efficiently, and you're back to linearly searching through the entries to find the correct key. The documentation of hash-based structures assumes a well-behaving hash code implementation. – lrn May 05 '22 at 10:54