Sets and maps in Dart: uniqueness and lookup

Write var x = {} and ask whether x is a Set: Dart answers false. An empty pair of braces is a Map, so a program meant to hold three tags starts with the wrong type and prints no warning. Maps and sets look alike on the page, and the small rules that keep them straight are easy to miss: the key that compares by identity when it should compare by value, the iteration order that four different classes under one word keep in four different ways.

This lesson counts a mixed Hindi-English sentence with update, runs set algebra on two teams’ skills, keys a seat map by a record so that (row: 'B', seat: 12) is one key, and measures the key order of three Map flavours in one run. Every number comes from a program you can run on the Dart SDK 3.13.5.

An empty pair of braces is a Map, not a Set

Both Set and Map use braces in their literals, and three rules decide which type a literal gives you. A literal with key: value pairs is a Map. A literal of plain values is a Set. An empty literal, with nothing to tell them apart, is a Map: Map has had {} since Dart’s first release, and keeping that meant that an empty literal could not quietly change its type when Set literals arrived in 2.2. Run this program and read each line against the three rules:

void main() {
  // An empty pair of braces is a Map, not a Set.
  final x = {};
  print('var x = {} is Map: ${x is Map}');
  print('var x = {} is Set: ${x is Set}');

  // To make an empty set, say what the elements are.
  final tags = <String>{};
  tags.add('offer');
  tags.add('offer');
  tags.add('festive');
  print('<String>{} after three adds: $tags');
  print('tags.length: ${tags.length}');

  // A literal with pairs is a Map; a literal of plain values is a Set.
  final prices = {'chai': 20, 'poha': 60, 'thali': 180};
  final cities = {'Pune', 'Mumbai', 'Pune', 'Delhi'};
  print('prices.runtimeType is Map: ${prices is Map}');
  print('cities.runtimeType is Set: ${cities is Set}');
  print('cities: $cities');
  print('cities.length: ${cities.length}');
}

var x = {} is Map: true
var x = {} is Set: false
<String>{} after three adds: {offer, festive}
tags.length: 2
prices.runtimeType is Map: true
cities.runtimeType is Set: true
cities: {Pune, Mumbai, Delhi}
cities.length: 3

var x = {} is a Map, so x is Set printed false. To make an empty set, name the element type: <String>{} is a set, and three adds of offer, offer and festive left a set of length 2, because a set drops duplicates silently. The non-empty literals went the other way: {'chai': 20, 'poha': 60, 'thali': 180} has pairs so it is a Map, and {'Pune', 'Mumbai', 'Pune', 'Delhi'} has plain values so it is a Set, which collapses the second Pune and prints {Pune, Mumbai, Delhi}.

Two slightly different ways say the type without a prefix: a context type, so final Set<String> tags = {} makes a set because the variable’s type asks for one, and a type argument on a constructor, as in Set<String>() or <String>{}. The analyzer picks the type from whichever one tells it the most.

The same two tools, a type argument on the literal and a context type on the variable, rescue a non-empty literal whose element type the compiler cannot work out, such as a heterogeneous <Object>{...} of mixed strings and integers. When the elements are of one type that infers cleanly, as in {20, 60, 180} of three ints, neither is needed; the inferred Set<int> is what you expect.

Set algebra: union, intersection and difference

A Set is the right type for a yes-or-no question about values, with no counts and no order to defend. Three operations run a set algebra on two sets. union returns a new set with every value of either side. intersection returns a new set with the values that are in both sides. difference returns a new set with the values of the first side that are not in the second. Each one gives you a new set, so neither input is touched. containsAll asks whether every value of a given set lies in another. contains on a single value runs in O(1) on average, which is why reaching for a Set is often a speed-up over a List.contains loop.

void main() {
  final backend = {'Dart', 'Postgres', 'Docker', 'HTTP', 'Linux'};
  final mobile = {'Dart', 'Flutter', 'HTTP', 'iOS', 'Android'};

  print('backend: $backend');
  print('mobile:  $mobile');
  print('union: ${backend.union(mobile)}');
  print('intersection: ${backend.intersection(mobile)}');
  print('only backend knows: ${backend.difference(mobile)}');
  print('only mobile knows: ${mobile.difference(backend)}');

  print('backend has every skill of [Dart, HTTP]: '
      '${backend.containsAll({'Dart', 'HTTP'})}');
  print('backend has every skill of [Dart, Flutter]: '
      '${backend.containsAll({'Dart', 'Flutter'})}');

  // Iteration keeps insertion order, as the LinkedHashSet documentation says.
  final order = <String>{};
  for (final name in ['Riya', 'Asha', 'Riya', 'Dev', 'Asha']) {
    order.add(name);
  }
  print('insertion order after five adds: ${order.toList()}');
}

backend: {Dart, Postgres, Docker, HTTP, Linux}
mobile:  {Dart, Flutter, HTTP, iOS, Android}
union: {Dart, Postgres, Docker, HTTP, Linux, Flutter, iOS, Android}
intersection: {Dart, HTTP}
only backend knows: {Postgres, Docker, Linux}
only mobile knows: {Flutter, iOS, Android}
backend has every skill of [Dart, HTTP]: true
backend has every skill of [Dart, Flutter]: false
insertion order after five adds: [Riya, Asha, Dev]

The intersection of a backend team’s skills and a mobile team’s skills gave {Dart, HTTP}, the two skills they share. backend.difference(mobile) kept {Postgres, Docker, Linux}, the skills only the backend team has, while mobile.difference(backend) gave {Flutter, iOS, Android}, the skills only the mobile team has. containsAll on {Dart, HTTP} answered true and on {Dart, Flutter} answered false, which is the question “could the backend team cover this list of required skills on paper?”

The last line matters for anyone who iterates a set. The default Set constructor and the set literal both give you a LinkedHashSet, which the API page describes as a set in which “iteration order is the insertion order of the first add of each element”. Five adds of Riya, Asha, Riya, Dev, Asha built the set [Riya, Asha, Dev] and kept that order; a HashSet from dart:collection has no such promise, so iteration there is in no order you can rely on.

Build counts and groups without the missing-key branch

Reading a key that is not in a Map returns null. That one rule turns every “look it up, bump it or make one” loop into a branch: a null has no +, and counts[word] + 1 would fail. Map has three operations that remove that branch and read better. update(key, (c) => c + 1, ifAbsent: () => 1) tries to update an existing entry and, when the key is new, runs the ifAbsent builderA callback that `Map.update` runs when a key is missing: it returns the value to store under that key. once to make a value. putIfAbsent(key, () => <String>[]) returns the existing value or writes a new one from the builder; it returns that value, so a chain like .add(word) works on either case. cache[key] ??= value writes only when the slot is null.

void main() {
  final sentence = 'namaste doston chai lao chai aur poha garam chai hai';

  // Build counts with update(..., ifAbsent: ...): one line per word, no missing-key branch.
  final counts = <String, int>{};
  for (final word in sentence.split(' ')) {
    counts.update(word, (c) => c + 1, ifAbsent: () => 1);
  }
  print('sentence: $sentence');
  print('counts: $counts');
  print('distinct words: ${counts.length}');
  print('chai appears ${counts['chai']} times');

  // A missing key returns null, so counts never throws when a word is absent.
  print('missing key counts["english"]: ${counts['english']}');

  // Another pattern that reads well: putIfAbsent plus a mutation.
  final byLetter = <String, List<String>>{};
  for (final word in sentence.split(' ')) {
    byLetter.putIfAbsent(word[0], () => <String>[]).add(word);
  }
  print('grouped by first letter: $byLetter');

  // The ??= operator writes a value only when the slot is null.
  final cache = <String, String>{};
  cache['chai'] ??= 'uploaded 2 s ago';
  cache['chai'] ??= 'uploaded now'; // skipped, chai is set
  cache['poha'] ??= 'uploaded now';
  print('cache after three ??= writes: $cache');
}

sentence: namaste doston chai lao chai aur poha garam chai hai
counts: {namaste: 1, doston: 1, chai: 3, lao: 1, aur: 1, poha: 1, garam: 1, hai: 1}
distinct words: 8
chai appears 3 times
missing key counts["english"]: null
grouped by first letter: {n: [namaste], d: [doston], c: [chai, chai, chai], l: [lao], a: [aur], p: [poha], g: [garam], h: [hai]}
cache after three ??= writes: {chai: uploaded 2 s ago, poha: uploaded now}

The sentence has chai three times and seven other words once each. update collected it into {namaste: 1, doston: 1, chai: 3, lao: 1, aur: 1, poha: 1, garam: 1, hai: 1}, with the keys in the order they first appeared. counts['english'] returned null without an exception, so the next line could compare it. The grouping step used putIfAbsent to make the list once and .add to extend it, so the chai group grew to three. The cache with ??= printed {chai: uploaded 2 s ago, poha: uploaded now}: the second write to chai did nothing, because the slot was no longer null. Step through the first words to see what update writes on each one:

Three slips are worth naming. counts[word]! + 1 writes “I promise this is not null” when the key is missing; Dart’s null check then throws, and the program ends. Reading counts[word] ?? 0 and writing back fixes it, but update with an ifAbsent reads better and runs the builder only when it has to. The second slip is a loop over counts.keys that reads counts[k] for every key: counts.entries gives you both at once, with pattern destructuring in Dart 3 that writes as for (final MapEntry(:key, :value) in counts.entries) and names what each piece is for.

A grouping function on grapheme clustersgrapheme cluster: What a reader sees as one character, as Unicode's UAX #29 defines it: one or more code points, such as स्ते or a family emoji. package:characters splits text into grapheme clusters. More in “Dart strings, interpolation and Unicode text”, so that अमित and Asha both land under one cluster each, lives in the strings and Unicode lesson. The exercise at the end of this lesson uses that reader-aware rule.

A record makes a map key by value, not by identity

Every Map looks up a key in two steps. It asks the key for its hashCodehash code: The integer every Dart object returns from its hashCode property, used by hash-based sets and maps to pick a bucket for the value. Two objects that compare equal with == must return the same hash code., which chooses a bucket, and then compares the keys in that bucket with == to find a match. Both come from the key’s class. String, int and other value types override both, so two separate String objects with the same characters are one map key. List overrides neither, so two separate List objects, even with the same elements, are two map keys. A List makes a poor key, as the list keys cache answer in the operators module shows.

A record is the easy fix in Dart 3: a recordrecord: An anonymous, immutable value that bundles a fixed set of positional and named fields, each with its own type. Records need no declaration and compare equal when their shape and fields are equal. More in “Records in Dart: several values without a class” defines == and hashCode from its shape and its field values, so (row: 'B', seat: 12) built again elsewhere is the same key as the one you stored under. A seat map keyed by (row: String, seat: int) carries two columns of a booking table in the type system; no | character to split a composite string key, no accidental collision between row B seat 12 and row B1 seat 2.

void main() {
  // A seat is a record of a row letter and a number. Records compare by shape and value,
  // so two separately built keys with the same row and seat are the same map key.
  final booked = <({String row, int seat}), String>{};
  booked[(row: 'B', seat: 12)] = 'Asha';
  booked[(row: 'B', seat: 13)] = 'Ravi';
  booked[(row: 'C', seat: 1)] = 'Meera';

  print('seat B12 holds: ${booked[(row: 'B', seat: 12)]}');
  print('seat C7 holds: ${booked[(row: 'C', seat: 7)]}');

  final k1 = (row: 'B', seat: 12);
  final k2 = (row: 'B', seat: 12);
  print('two keys built separately, k1 == k2: ${k1 == k2}');
  print('hashCodes equal: ${k1.hashCode == k2.hashCode}');
  print('identical(k1, k2): ${identical(k1, k2)}');

  // Entries destructure with the pattern MapEntry(:key, :value).
  print('every booked seat:');
  for (final MapEntry(:key, :value) in booked.entries) {
    print('  ${key.row}${key.seat} -> $value');
  }

  // A List is a poor key, because list == is identity, not contents.
  final listKeyed = <List<int>, String>{};
  listKeyed[[2, 12]] = 'Asha';
  print('listKeyed[[2, 12]] on a fresh list: ${listKeyed[[2, 12]]}');
}

seat B12 holds: Asha
seat C7 holds: null
two keys built separately, k1 == k2: true
hashCodes equal: true
identical(k1, k2): false
every booked seat:
  B12 -> Asha
  B13 -> Ravi
  C1 -> Meera
listKeyed[[2, 12]] on a fresh list: null

The lookup for (row: 'B', seat: 12) found Asha, and the lookup for an unbooked seat returned null. Two keys built in separate expressions were == with equal hash codes, and identical on them was still false: the records are two separate objects, and the map doesn’t care, because it reads only hashCode and ==. Iteration printed each MapEntryMapEntry: The pair of a key and its value that a Map iterates with map.entries. Dart 3's pattern MapEntry(:key, :value) destructures each entry into two named variables in one line. in insertion order, and the destructuring pattern MapEntry(:key, :value) unpacked each entry’s two sides in one step.

The last line is the identity trap. listKeyed[[2, 12]] = 'Asha' wrote under one list, and listKeyed[[2, 12]] read from another list of the same contents. The second list has a different hashCode, lands in a different bucket, and the lookup returns null. A record, or a small class with final fields and overridden == and hashCode, prevents the whole class of bugs the identity default hides.

Three map flavours, with the order each one keeps

The default Map the brace literal gives you is a hash-based maphash-based map: A map that finds a key in two steps: it reads the key's hashCode to choose a bucket and compares the keys in that bucket with ==. LinkedHashMap and HashMap in dart:collection are both hash-based. that happens to keep insertion order on the side: a LinkedHashMap, in dart:collection. Three concrete classes sit under the Map interface, and the choice is about iteration order and about what the key type is:

• LinkedHashMap tracks a linked list of entries in the order they were first written, so iteration follows that order. The default {} literal and the Map constructor both give you one.
• HashMap keeps no such list, so iteration goes in whatever order the hash buckets happen to lie in.
• SplayTreeMap is a self-balancing binary search tree keyed by compareTo, so iteration gives the keys in sorted order and firstKey and lastKey return the smallest and the largest in O(log n).

Run the same five inserts through each of them:

import 'dart:collection';

void main() {
  // Five store codes added in a fixed order, so the three flavours can be compared.
  const added = ['pune', 'mumbai', 'bengaluru', 'delhi', 'chennai'];
  const sales = {
    'pune': 120,
    'mumbai': 400,
    'bengaluru': 250,
    'delhi': 980,
    'chennai': 180,
  };

  // The default Map literal is a LinkedHashMap: iteration keeps insertion order.
  final linked = <String, int>{};
  for (final city in added) {
    linked[city] = sales[city]!;
  }
  print('LinkedHashMap keys: ${linked.keys.toList()}');

  // HashMap gives no order guarantee.
  final hashed = HashMap<String, int>();
  for (final city in added) {
    hashed[city] = sales[city]!;
  }
  print('HashMap keys: ${hashed.keys.toList()}');

  // SplayTreeMap keeps the keys sorted, by the natural order of String.
  final sorted = SplayTreeMap<String, int>();
  for (final city in added) {
    sorted[city] = sales[city]!;
  }
  print('SplayTreeMap keys: ${sorted.keys.toList()}');

  // The same five entries, three orderings.
  print('added order:   $added');
  print('linked first:  ${linked.keys.first}');
  print('sorted first:  ${sorted.keys.first}');
  print('sorted last:   ${sorted.keys.last}');
}

LinkedHashMap keys: [pune, mumbai, bengaluru, delhi, chennai]
HashMap keys: [chennai, mumbai, delhi, pune, bengaluru]
SplayTreeMap keys: [bengaluru, chennai, delhi, mumbai, pune]
added order:   [pune, mumbai, bengaluru, delhi, chennai]
linked first:  pune
sorted first:  bengaluru
sorted last:   pune

The LinkedHashMap’s keys came out [pune, mumbai, bengaluru, delhi, chennai], the order the loop added them in. The HashMap’s keys came out [chennai, mumbai, delhi, pune, bengaluru], which looks like no order on this page; nothing in the API promises any particular order, and the class documentation adds that iteration order can change between SDK versions, so code that relies on this run’s output will quietly go wrong one day. The SplayTreeMap’s keys came out [bengaluru, chennai, delhi, mumbai, pune], which is String.compareTo order, so it starts with bengaluru and ends with pune in every run.

A fourth flavour serves a different question. Queue and its default class ListQueueFIFO queue: A collection that serves items first-in, first-out: additions go at the back and removes come from the front. dart:collection's Queue and its ListQueue class work that way, with amortised O(1) at both ends. from dart:collection are not maps at all; they serve items in first-in, first-out order, as the next section shows. Decide between the four by answering two questions about iteration order and the main operation. The table rules out the three that do not fit:

Sets have the same three flavours, under the same names with Set where Map sits: LinkedHashSet is the default and keeps insertion order; HashSet keeps no order; a SplayTreeSetsplay tree: A self-balancing binary search tree that moves a looked-up node to the root, so a key read often becomes cheap. SplayTreeMap and SplayTreeSet in dart:collection use one, keyed by compareTo. keeps the elements sorted. The choice is the same question read against values rather than keys.

A ListQueue serves items in the order they arrived

Many programs need a sequence that keeps order and lets you take from one end while adding to the other: a worker that processes uploads in the order they arrived, a scheduler that runs each pending job once. A Map is wrong for that work, because a map’s remove takes a key, not the oldest or the newest entry. dart:collection gives you Queue, an interface, and ListQueue, its default concrete class, built on a growable ring buffer so that addLast at the back and removeFirst at the front both run in amortised O(1) time.

import 'dart:collection';

void main() {
  // A ListQueue is a FIFO queue: addLast at the back, removeFirst from the front.
  final queue = ListQueue<String>();
  queue.addLast('upload-01.jpg');
  queue.addLast('upload-02.jpg');
  queue.addLast('upload-03.jpg');

  print('queue: $queue');
  print('length: ${queue.length}');
  print('next in line: ${queue.first}');

  while (queue.isNotEmpty) {
    final next = queue.removeFirst();
    print('processing $next');
  }
  print('queue is empty: ${queue.isEmpty}');

  // Both ends are supported, so a ListQueue is also a deque.
  final deque = ListQueue<int>();
  deque.addLast(2);
  deque.addLast(3);
  deque.addFirst(1);
  deque.addLast(4);
  print('deque after addFirst(1) and three addLasts: $deque');
  print('removeFirst: ${deque.removeFirst()}');
  print('removeLast: ${deque.removeLast()}');
  print('remaining: $deque');
}

queue: {upload-01.jpg, upload-02.jpg, upload-03.jpg}
length: 3
next in line: upload-01.jpg
processing upload-01.jpg
processing upload-02.jpg
processing upload-03.jpg
queue is empty: true
deque after addFirst(1) and three addLasts: {1, 2, 3, 4}
removeFirst: 1
removeLast: 4
remaining: {2, 3}

Three addLast calls put three uploads in the queue, and the while loop processed them as upload-01.jpg, upload-02.jpg, upload-03.jpg, oldest first. A ListQueue is also a deque: it accepts addFirst, removeLast and random reads, which the deque test did by putting 1 at the front, three items at the back, and ending with {2, 3} after a removeFirst and a removeLast. The removeFirst returned 1, the oldest, and removeLast returned 4, the newest, which is why only 2, 3 were left.

A Map has one more read-only form worth knowing: Map.unmodifiableOf(source), new in Dart 3.13, copies the entries of source into a map that refuses writes, with better typing than the older Map.unmodifiable. A short API that returns a Map and does not want callers to change it hands out an unmodifiableOf copy; the caller still reads it the same way.

Practise: group by first grapheme and find common skills

Make a console project with dart create -t console map_lab and work in bin/map_lab.dart. Add dart pub add characters so the first function can be reader-aware. Then write two functions, each one tested on your own small inputs before you move on:

1. Map<String, List<String>> groupByInitial(List<String> names) groups names by the first grapheme cluster of each name, so ['Asha Rao', 'अमित शाह', 'ananya'] gives {A: [Asha Rao, ananya], अ: [अमित शाह]} when the match is case-insensitive for Latin letters. Use putIfAbsent to make the inner list once per group, and read the first cluster through name.characters.first so that अमित groups under अ, not under one of its code units.
2. Set<String> commonSkills(List<Set<String>> teams) returns the skills every team has, with an empty set when the list of teams is empty. Start from the first team as the seed, fold the rest with intersection, and read the first-team-missing test as a special case before the loop.

Make a console project with dart create -t console map_lab, add dart pub add characters, and check each function against the examples above, then against an empty list of names and an empty list of teams. When both pass, work through the self-check. The idea you are least sure of comes first, and every choice explains itself.

Interview questions

Warm-up (fresher): Why does var x = {} print Map for runtimeType, and how do you write an empty set?

Dart decides which type a literal gives in three rules: a brace literal with key: value pairs is a Map, a brace literal of plain values is a Set, and an empty brace literal is a Map. The empty case kept its meaning from Dart 1, so that older code that wrote {} for an empty map did not quietly change type when set literals arrived in Dart 2.2. For an empty set, say what the elements are, either with a type argument on the literal, <String>{}, or with a context that names the type, as in final Set<String> tags = {}. The compiler then infers a set and the analyzer accepts tags.add('offer'). The same two tools fix a non-empty literal whose type cannot be inferred, such as a heterogenous <Object>{...}.

Two deeper questions in the module’s bank build on the measurements of this lesson. Think about what you would try first on each, then open the discussion for the model answer:

Key takeaways

• An empty {} is a Map, a brace literal with pairs is a Map and a brace literal of plain values is a Set; write <String>{} or a context type to make a set.
• A Set runs union, intersection, difference and containsAll in O(1) on average per element, and the default LinkedHashSet keeps iteration in the order each value was first added.
• Reading a missing key returns null; use update(key, ..., ifAbsent: ...), putIfAbsent or cache[key] ??= v to keep the “lookup, bump or make one” shape in one call.
• A map looks up a key by hashCode and ==, so records, with their value-based == and hashCode, make good composite keys, while a List key makes two look-alike lists two different keys.
• The default {} literal is a LinkedHashMap and keeps insertion order; a HashMap promises no order and a SplayTreeMap keeps the keys sorted by compareTo.
• dart:collection’s ListQueue is a FIFO queue and a deque: addLast and removeFirst run in amortised O(1), and the three map flavours have the same sibling sets under LinkedHashSet, HashSet and SplayTreeSet.