skip to content

In Dart, what iteration order does a Map or Set literal guarantee, and when would you choose HashMap or SplayTreeMap instead?

level: middleimportance: should knowfreq 40%

answer

  1. literals are linked hash tables
  2. first insertion decides position
  3. remove and re-add moves last
  4. {} alone is a Map
  5. unordered versus sorted alternatives

basics

~10 s

Dart map and set literals create a LinkedHashMap or LinkedHashSet, which iterate in key insertion order. Pick HashMap when order truly does not matter, and SplayTreeMap when keys must stay sorted by a comparator.

solid answer

~40 s

A non-constant map literal, `Map()` and `Map.of` create a `LinkedHashMap`; set literals and `Set()` create a `LinkedHashSet`. Both are hash tables that remember **insertion order**: keys, values and entries iterate in the order keys were first added. Assigning a new value to an existing key keeps its position; removing it and adding it again moves it to the end. `HashMap` drops that bookkeeping and guarantees no order at all, so use it only when order is irrelevant. `SplayTreeMap` keeps keys **sorted** by a comparator, at O(log n) cost, which suits an index read in sorted order many times. Insertion order is not sorted order: for a one-off ranking, sort `entries`. And `{}` by itself is a map, so an empty set needs `<String>{}`.

code

dart · 14 lines
dart
import 'dart:collection';

void main() {
  const words = ['pear', 'apple', 'fig', 'apple'];

  final firstSeen = <String>{}..addAll(words);
  print(firstSeen); // {pear, apple, fig}

  final sorted = SplayTreeMap<String, int>();
  for (final w in words) {
    sorted.update(w, (n) => n + 1, ifAbsent: () => 1);
  }
  print(sorted); // {apple: 2, fig: 1, pear: 1}
}

go deeper

for a junior

Remember that map and set literals keep insertion order and that empty braces make a map, not a set.

for a middle

Explain LinkedHashMap's rules for updates versus remove-and-re-add, and contrast HashMap and SplayTreeMap in order and cost.

for a senior

Choose the container from real access patterns, avoid tests that depend on HashMap order, and sort entries explicitly with a tie-breaker when output must be deterministic.

for a principal

Decide where ordering is part of a data contract, such as serialized output, and make it explicit rather than an accident of the default map.

## The default Map and Set are linked hash tables In Dart, a non-constant map literal such as `{'a': 1}` creates a **`LinkedHashMap`**, and so do `Map()`, `Map.of` and `Map.from`. Likewise, a set literal `{'a', 'b'}` and `Set()` create a **`LinkedHashSet`**. Both are hash tables with expected constant-time lookup, plus a record of **insertion order**: - keys (and therefore `values` and `entries`) iterate in the order the keys were **first inserted**; - **assigning a new value to an existing key does not move it**; - **removing a key and adding it again moves it to the end**; - for a set, adding an element that is already present leaves the set unchanged and returns `false` from `add`. So `jsonEncode`, `toString`, `for (final e in map.entries)` and `map.keys.first` all see keys in a predictable order across runs. ## Word frequencies, in order ```dart final counts = <String, int>{}; for (final word in ['to', 'be', 'or', 'not', 'to', 'be']) { counts.update(word, (n) => n + 1, ifAbsent: () => 1); } print(counts); // {to: 2, be: 2, or: 1, not: 1} counts.remove('to'); counts['to'] = 2; print(counts.keys); // (be, or, not, to) ``` Updating `to` and `be` did not reorder them; removing and re-adding `to` pushed it to the end. ## The empty-braces trap `{}` on its own is a **map**, because map literals came first. To get an empty set you need a type argument or a declared type: ```dart var names = <String>{}; // Set<String> Set<String> tags = {}; // Set<String> var oops = {}; // Map<dynamic, dynamic> ``` ## The alternatives in dart:collection | Class | Iteration order | Lookup | Keys need | |---|---|---|---| | `LinkedHashMap` (the default) | insertion order | hash, expected O(1) | `==` and `hashCode` | | `HashMap` | unspecified, stable only until the map is modified | hash, expected O(1) | `==` and `hashCode` | | `SplayTreeMap` | sorted by a comparator | tree, O(log n) amortized | a `compare` function or `Comparable` keys | Choosing among them: 1. Keep the **default** when you want predictable output or "first seen" order — the common case, and the reason the literal is linked. 2. Use **`HashMap`** only when order is irrelevant and you have measured that the bookkeeping for insertion order matters; "unordered" means you must not rely on any order at all, including in tests. 3. Use **`SplayTreeMap`** (or `SplayTreeSet`) when you repeatedly need keys **sorted**, for example an alphabetical word index that is read many times while words keep arriving. For a one-off report, sorting `entries` once is simpler. ## Sorting is not an ordering guarantee Insertion order is not sorted order. If a frequency report must list the most frequent words first, sort a copy of the entries: ```dart final top = counts.entries.toList() ..sort((a, b) => b.value.compareTo(a.value)); ``` `List.sort` is **not guaranteed stable**: entries that compare equal may come out in any order. Add a tie-breaker (for example `a.key.compareTo(b.key)`) when the output must be deterministic. ## Modifying while iterating Adding or removing keys while iterating `keys`, `values` or `entries`, or inside a `forEach` callback, is not allowed; the default implementation throws a `ConcurrentModificationError`. Changing the value of an existing key does not change the key set. To delete entries in bulk, use `removeWhere((key, value) => ...)`, or collect the keys first and remove them afterwards. ## Interview summary - Literal maps and sets are **LinkedHash**; order is insertion order, not sorted order. - Re-assigning a value keeps position; remove-then-add moves it last. - `{}` alone is a map. - `HashMap` gives up any order; `SplayTreeMap` keeps keys sorted at tree cost.

  • In a Dart LinkedHashMap, does counts['to'] = 3 move an existing 'to' key to the end?
    No. Changing the value of a key that is already present keeps its position. Only removing the key and inserting it again places it last in the iteration order.
  • What order does a Dart HashMap iterate in?
    An unspecified one. It stays the same while the map is unmodified, but any insertion or removal may change it, so code and tests must not depend on it. Use the default `LinkedHashMap` or a `SplayTreeMap` if order matters.
  • What is wrong with var tags = {}; when you meant a set of strings in Dart?
    Empty braces default to a map literal, so `tags` is a `Map<dynamic, dynamic>`. Write `<String>{}` or declare `Set<String> tags = {};` to get a `LinkedHashSet<String>`.

saying these in an interview costs you the question

  • A Dart Map literal iterates in random hash order.
  • Default Dart maps iterate keys in sorted order.
  • Updating a value moves its key to the end.
  • var s = {}; creates an empty Set.
  • HashMap keeps insertion order like the literal.