Time complexity of Map containsKey and containsValue in Dart
What is the time complexity of
Map.containsValue in Dart? I'd like to know for the following implementations:
I assume for the hash map implementations
containsKey is amortized constant time and
containsValue is probably linear time. For
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.)
containsKey, it's the same time as doing a lookup.
LinkedHashMap: Expected constant time, worst-case linear time for degenerate
SplayTreeMap, ammortized logarithmic time.
containsValue, it's linear in the number of elements (at least). It simple 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. Some potential
HashMapimplementations 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.