skip to content

Why can a Dart Map or Set fail to find a key that was inserted earlier, and how do == and hashCode cause it?

level: seniorimportance: should knowfreq 34%

answer

  1. hashCode picks the bucket, == confirms
  2. lists are equal only to themselves
  3. records compare structurally
  4. never mutate a stored key
  5. LinkedHashMap accepts equals and hashCode

basics

~20 s

Dart hash maps and sets locate keys by hashCode, then confirm with ==. A key without value equality (a List or plain class), a key mutated after insertion, or inconsistent == and hashCode makes an entry exist yet be unfindable.

solid answer

~50 s

`LinkedHashMap`, `LinkedHashSet`, `HashMap` and `HashSet` use the key's `hashCode` to pick a bucket and `==` to confirm a match, and they require equal keys to have equal hash codes and keys not to change while stored. Lookups fail when that breaks: a class without value equality or a `List` key compares by identity, so a new but equal-looking instance finds nothing; a key object mutated after insertion now hashes to a different bucket; and `==` that disagrees with `hashCode` makes lookups hit or miss by chance. Prefer immutable value keys — `String`, `int`, enums, or a record like `(word, line)`, which has structural `==` and `hashCode` for free. When the key type cannot change, give the map its own rules with `LinkedHashMap(equals: ..., hashCode: ...)`, or use `Map.identity()` when identity really is what you mean.

code

dart · 16 lines
dart
class WordKey {
  WordKey(this.text);
  String text; // mutable, and no == or hashCode override
}

void main() {
  final seen = <WordKey>{};
  final key = WordKey('dart');
  seen.add(key);

  print(seen.contains(WordKey('dart'))); // false: identity equality
  print(seen.contains(key)); // true: same instance

  final pairs = <(String, int), String>{('dart', 1): 'first line'};
  print(pairs[('dart', 1)]); // first line: records compare by value
}

go deeper

for a junior

Know that map and set keys are matched by == and hashCode, and that strings, numbers and records make safe keys.

for a middle

Explain why List and plain class keys use identity, and what happens to an entry when its key is mutated after insertion.

for a senior

Diagnose unfindable entries from symptoms, choose immutable or record keys, and apply LinkedHashMap custom equality or Map.identity where they fit.

for a principal

Set guidelines for which types may be used as collection keys and require key types to be immutable in shared models.

## How a hash-based Map or Set finds a key The default Dart `Map` (`LinkedHashMap`) and `Set` (`LinkedHashSet`), as well as `HashMap` and `HashSet`, are **hash tables**. A lookup works in two steps: 1. compute the key's `hashCode` to find a bucket; 2. compare the candidate keys in that bucket with `==`. For that to work, the keys must obey a contract stated in the `dart:collection` docs: `==` is a stable equivalence relation, **equal objects have equal hash codes**, and a key's hash code and equality **must not change while it is in the table**. When the contract breaks, the behaviour is unspecified — in practice, entries that exist but cannot be found. ## Four ways a key goes missing | Cause | What happens | |---|---| | class without value equality | two objects with the same fields are different keys; lookup with a new instance returns `null` | | `List` or `Map` used as a key | lists are equal only to themselves, so `[1, 2]` never finds a key stored as another `[1, 2]` | | key mutated after insertion | its hash code changes; the entry sits in the old bucket and `containsKey` returns `false` | | `==` and `hashCode` disagree | equal objects land in different buckets; lookups succeed or fail by accident | The first two come from **identity equality**: `Object`'s default `==` is `identical`, and `List` keeps that default — the `List` docs state that lists are, by default, only equal to themselves and do not compare elements. ## Choosing good keys - **Strings, numbers, enums, `bool` and `DateTime`** have value equality and are the safest keys. - **Records** get structural `==` and `hashCode` automatically, so a composite key such as `(String, int)` works without writing any code: `counts[(word, lineNo)]` finds the entry created by an equal record. - A **class** used as a key needs a matching `==`/`hashCode` pair and should be immutable; how to write that pair is its own topic, and the danger here is only that a key's equality must not change while it is stored. - A **list of words** as a key: convert it to a string (`words.join(' ')`) or a record, rather than relying on list equality. ```dart final bigrams = <(String, String), int>{}; bigrams.update(('to', 'be'), (n) => n + 1, ifAbsent: () => 1); print(bigrams[('to', 'be')]); // 1 - an equal record finds it final byList = <List<String>, int>{}; byList[['to', 'be']] = 1; print(byList[['to', 'be']]); // null - a different list instance ``` ## When you cannot change the key class `LinkedHashMap` and `LinkedHashSet` accept custom equality without touching the key type: - `LinkedHashMap<K, V>(equals: ..., hashCode: ..., isValidKey: ...)` uses your functions instead of `==` and `hashCode`. Supply both or neither; `isValidKey` protects the functions from lookups with keys of the wrong type (the default accepts instances of `K`). - `LinkedHashMap.identity()`, also reachable as `Map.identity()` and `Set.identity()`, compares keys with `identical` and `identityHashCode`, which is right for tracking **which object instances** you have seen, such as visited nodes in a graph that may contain equal-looking nodes. For example, a case-insensitive word counter: ```dart import 'dart:collection'; final counts = LinkedHashMap<String, int>( equals: (a, b) => a.toLowerCase() == b.toLowerCase(), hashCode: (s) => s.toLowerCase().hashCode, ); ``` Normalising the key before inserting (`word.toLowerCase()`) is usually simpler; custom equality earns its place when the original spelling of the first occurrence must be kept. ## Diagnosing a "lost" entry 1. Print `map.length` and the keys: if the entry is listed but `map[key]` returns `null`, it is an equality or hashing problem, not a missing insert. 2. Check the key type: a `List`, `Map`, `Set` or a class without value equality means identity comparison. 3. Look for mutation of a key object after it was inserted, including fields changed by other code holding the same reference. 4. Check that `==` and `hashCode` use the same fields. Fix the key, not the lookup: switch to an immutable value key (a `String`, a record, an immutable class) or give the map an explicit `equals`/`hashCode`.

  • Why does a Dart Set<List<int>> accept [1, 2] twice?
    `List` keeps `Object`'s identity equality, so two separately created lists with the same elements are different elements to the set. Use a record, a joined `String`, or a `LinkedHashSet` built with custom `equals` and `hashCode` functions when content should decide membership.
  • When is Map.identity() the right choice in Dart?
    When the question is "have I seen this exact object?" rather than "have I seen an equal value?" — for example tracking visited nodes in an object graph where two nodes may compare equal. It compares keys with `identical` and `identityHashCode` while keeping insertion order.

A hash map is a cloakroom that files your coat under the number on your ticket. If the ticket's number changes while the coat hangs there, or you bring a different ticket that merely looks the same, the attendant searches the wrong hook and says the coat is not there.

saying these in an interview costs you the question

  • Two lists with the same elements are the same Map key.
  • Mutating a key object inside a Set is safe.
  • Records must override hashCode to work as keys.
  • hashCode alone decides whether two keys match.
  • A missing lookup means the insert never happened.