Every Built-in Method: Set & Map

After this lesson you will know what a Dart Set and Map look like inside memory (a compact hash table, a chained hash table, and a splay tree), why a lookup is O(1) in one and O(log n) in another, and you will have seen every public member of Set, Map, MapEntry and of the implementations HashSet, LinkedHashSet, SplayTreeSet, HashMap, LinkedHashMap and SplayTreeMap with its cost, the exceptions it can throw, whether it changes the collection or returns something new, and a runnable example whose exact output was checked against the real Dart SDK. Related lessons: D08 Collections, D22 Mutability, D26 List.

Source of truth: the Dart SDK 3.11 sources (core/set.dart, core/map.dart, core/iterable.dart, collection/hash_set.dart, hash_map.dart, linked_hash_set.dart, linked_hash_map.dart, splay_tree.dart) and the VM implementations _internal/vm_shared/lib/compact_hash.dart and collection_patch.dart. Complexities and table sizes describe the native VM / AOT; on the web (dart2js) the collections are built differently and int.hashCode differs. Every printed result was produced by running the code with Dart 3.11 and is asserted in verify/d27.dart.

1. What a Set and a Map really are

Words, defined once. A hash code is a whole number computed from a value (key.hashCode) that tells the machine roughly where to file it. A hash table is an array of slots in which values are filed by hash code. A collision is two different keys wanting the same slot. A tree is a structure where each node has up to two children (a smaller side and a larger side). Insertion order means iteration returns things in the order they were first added.

Set and Map are only promises (abstract interfaces). The real work is done by six classes in dart:collection. You get one of them every time you write a literal:

First look at all three side by side. In each player the variable lives on the stack, the collection object on the heap, and below it the real storage (arrays, buckets, tree) changes as the statement runs. Press play and read the captions: they name every decision.

The default: LinkedHashMap

HashMap

SplayTreeMap

2. Inside the three implementations

Hashing and the equality contract

Both hash-based classes do the same two-step dance for every lookup: (1) compute key.hashCode and use it to jump to one place; (2) compare the keys found there with ==. For this to work the contract must hold: if a == b then a.hashCode == b.hashCode (the reverse need not hold: different objects may share a hash). Break it and equal keys go to different places and are never compared.

On the native VM, int.hashCode is not the number itself: for small non-negative ints it is the number times 11601 (an odd constant that mixes the bits; the simulators below use exactly that and the page asserts it for 0..90 000). Strings, doubles and your own classes have other hash codes. The simulators therefore accept keys 0..999.

HashSet / HashMap: chained buckets

The table is an array of buckets (starting with 8). A key goes to bucket hashCode & (buckets - 1) (because the size is a power of two, that is "the last bits of the hash"). Each bucket holds a chain: a little linked list of entry objects (key, value, hash, next). A new entry is pushed on the front of its chain. When the table is more than 75% full (count × 4 > buckets × 3) it doubles and every entry is re-filed, which reverses chain order. Iteration visits bucket 0, 1, 2, ... and each chain from the front: that is the order you see.

Watch three keys collide (5, 13, 21 all end in bucket 5 of an 8-bucket table), then a lookup that has to walk the chain:

The growth rule in action: the 7th entry makes 7×4 = 28 > 8×3 = 24, so the table doubles. Notice how the iteration order of the same elements changes:

The same structure as a small Dart class (this is the model that the interview question "reproduce the SDK HashMap order" asks for; its key order is asserted equal to the real HashMap on thousands of random operations):

Why the bad cases matter. If many keys share a bucket, a lookup walks a long chain. A weak hashCode (here k % 2, only two buckets are ever used) turns O(1) into O(n):

Now play with your own keys (0..999). Try keys that are multiples of 8 and watch the chain grow, then add enough keys to see a resize:

Input size → what is feasible: a HashMap with a decent hash handles 10⁶ inserts in well under a second; the same map with a constant hashCode would do 10⁶²/2 = 5·10¹¹ comparisons (minutes). Quality of hashCode is the whole game.

LinkedHashSet / LinkedHashMap: compact index + data

The default collection stores things in two arrays. The _data array simply holds the entries in the order they were added (key, value, key, value ... for a map). The _index array is the hash table: a power-of-two array of small numbers in which each used slot says "entry number n lives in _data". To look up a key: compute hashCode, shuffle it (((h & mask) × 3) & mask) to get a first slot, then probe slot after slot (linear probing: if the slot holds a different key, try the next one) until you find the key or hit an empty slot (0). Because the data array is in insertion order, iteration order is insertion order for free and iteration is a plain walk over an array.

Sizes (from the SDK source; they are not observable from Dart code): the first insert allocates an index of 8 slots and room for 4 entries. The index always has twice as many slots as there are entry places (load factor at most 1/2), so a miss usually ends after one or two probes. When the data array is full the table is rebuilt: twice as big, or the same size if more than half of the used entries are deleted. Removing an entry writes a DELETED marker (1) into its index slot and a deleted marker into its data entry; nothing moves, and the marker is cleaned out by the next rebuild. Updating the value of an existing key changes it in place: the key keeps its position.

Remove, re-add and overwrite show where tombstones and "moves to the end" come from:

The same idea in plain Dart (the interview solution "your own hash map" is a variant; this class keeps insertion order like the SDK, and its key order is asserted equal to the real LinkedHashMap on random operations):

Experiment with your own sequence (keys 0..999). Try removing a key and adding it back, then adding five different keys to see the rebuild:

Input size → what is feasible: 10⁶ inserts into the default map take a fraction of a second (a rebuild copies the entries, about 2 copies per entry in total, amortised O(1)); iterating is a plain array walk.

SplayTreeSet / SplayTreeMap: a self-adjusting tree

A binary search tree keeps smaller keys in the left subtree and larger keys in the right, so lookup walks down comparing: O(depth). A plain BST can degrade into a chain (inserting 1, 2, 3, 4 in order). A splay tree repairs this without bookkeeping: after every access (insert, lookup, remove, even a miss) it rotates the node it ended on up to the root. Frequently used keys stay near the top, and a deep node costs a lot once but halves the depth of the path it was on. The guarantee is O(log n) amortised (averaged over a sequence), while a single operation can be O(n). Two consequences you must remember: (1) reads change the tree (the contents stay, the shape changes); (2) equality is decided only by compare == 0.

Insert 1, 2, 3, 4 in ascending order (each new node becomes the root with the old root on its left), then look up key 1, the deepest node:

A balanced-looking tree: each lookup, even a miss, ends with the last visited node as the root:

The algorithm, as the SDK implements it (_splay, top-down: it rotates and detaches pieces on the way down instead of recursing back up). This class counts key comparisons so you can measure the cost:

Your turn (keys 0..999). Insert in ascending order, then look up the smallest key, and compare the depth before and after:

Input size → what is feasible: 10⁶ operations on a splay tree cost about 10⁶ × 20 = 2·10⁷ comparisons amortised; a hash map does the same job with ~10⁶ steps. Choose a SplayTree only when you need sorted iteration or predecessor / successor queries.

3. Every member, grouped by purpose

Each card shows: the signature, what it means in plain words, a badge telling you what happens to the collection, the cost and why (the structure from section 2), the exceptions, and a runnable example with its exact output.

The players use a mini-language so you can type your own experiments. The first part names the collection: set[3,1,2] (default LinkedHashSet), hset[...] (HashSet), tset[...] (SplayTreeSet), map{1:10,2:20} (default LinkedHashMap), hmap{...} (HashMap), tmap{...} (SplayTreeMap); options: hset(mod3)[...] uses a custom hashCode of k % 3 (mod2 .. mod9), tset(desc)[...] compares descending, tset(mod10)[...] compares by last digit. Then operations separated by ;, for example set[3,1,2] ; add 4 ; remove 3 ; removeWhere even. Keys and elements are whole numbers 0..999 (the hash simulation assumes them), map values −999..999, at most 12 values and 12 operations. A predicate is even, odd, >N, <N or =N; for maps write removeWhere k >5 or removeWhere v even; update 3 +5 ifAbsent 0; lists are [1,2], maps {1:2,3:4}.

3.1 Create: constructors and literals

How a Set or Map is created decides its kind (linked, hash, tree), whether it is mutable, and how elements are compared. The literal and Set() / Map() give the default linked kind; .of / .from copy; .unmodifiable freezes a copy; .identity compares by object identity. Input size → feasible: building from n elements costs n hash inserts: 10⁶ is a few hundred milliseconds.

3.2 The six implementations: their constructors

These are the constructors that belong to the concrete classes: they add the options equals / hashCode (hash kinds) and compare (tree kinds), and the .identity variants. Remember the rules of thumb: give equals and hashCode together; a tree's compare must be a consistent total order, and compare == 0 is equality there.

3.3 Read and inspect

Reading does not change a hash-based collection: it hashes, jumps to a slot, compares. On a SplayTree every read rotates the found node (or the last node on the path) to the root. Remember: [] returns null for a missing key; containsValue is the one lookup with no index (O(n)). Input size → feasible: 10⁶ lookups in a hash map: ~10⁶ steps; 10⁶ calls to containsValue on a 10⁵ map: 10¹¹ steps, far too slow, so keep a reverse map.

3.4 Add and put

Adding a new element is O(1) expected and amortised (the arrays or buckets double now and then), O(log n) amortised in the tree. Adding an element that is already there changes nothing for a set (and add says so with false) and replaces the value for a map (keeping its position in a linked map). Input size → feasible: 10⁶ adds ~ 0.1–0.3 s.

3.5 Remove

Removing by key is O(1) expected (a tombstone in the linked table, an unlink in a chain) and O(log n) amortised in the tree. The bulk forms (removeWhere, retainWhere, removeAll, retainAll) first collect what to remove and then remove it, so they are safe to call but not free: O(n). The collection is never shrunk automatically except by clear and by the linked table's rebuild. Input size → feasible: one removeWhere over 10⁶ elements ~10⁶ steps; removing keys inside a for loop over the same collection throws ConcurrentModificationError.

3.6 Set algebra

union, intersection and difference return new sets and leave both inputs alone; the other members here test or edit in place. The order of the result follows the receiving set's kind: insertion order for the default, bucket order for a HashSet, sorted for a SplayTreeSet. Input size → feasible: two sets of 10⁵ elements: ~2·10⁵ hash operations; calling contains on a List inside a loop instead would be 10¹⁰.

3.7 Views and transforms

Several members return views instead of copies. keys, values and entries are live windows on the map; cast is a typed window; Map.map is eager and builds a new map; forEach just loops. Step through what lives where:

3.8 SplayTree extras: sorted-map queries

Only SplayTreeMap has firstKey, lastKey, lastKeyBefore and firstKeyAfter (and a SplayTreeSet's first / last are the same idea). They splay too, so they change the tree's shape though never its contents. Input size → feasible: 10⁵ predecessor queries on 10⁵ keys ~ 10⁵ × 17 = 1.7·10⁶ comparisons; a hash map cannot answer them at all without scanning.

3.9 Inherited from Iterable (the Set side)

A Set is an Iterable, so every Iterable member works on it, in the set's own order. A Map is not an Iterable (iterate keys, values or entries). The members that return an Iterable (map, where, take ...) are lazy and redo their work on every new loop. Because a Set cannot be indexed, skip, elementAt and last-style members walk from the start. One more detail: a chain made only of map, take and skip still knows its length, so toList() can return an empty list without pulling a single element when that length is 0. (Lesson D25 covers Iterable in depth.) Input size → feasible: a chain over 10⁶ elements ~10⁶ steps per pass; iterating the same lazy chain 1000 times repeats that 1000 times, so call toList() or toSet() once.

fold and reduce squash the whole set into one value:

3.10 MapEntry

A MapEntry is one key/value pair as an object. It is immutable, and entries hands out a fresh snapshot each time you iterate. Watch the difference between a view of the map and a snapshot of a pair:

3.11 Object-level members

Every collection inherits five members from Object. The important one: == is identity for Set and Map. See it with two sets that hold the same elements, then with your own:

4. Mutable vs immutable sets and maps

"Mutable" means the object can change after it is made. Whether you can change a Set or Map depends on how it was made, and which members throw:

Four traps follow from "variables hold references": aliasing (two names, one map), shallow copy (the map is copied but the lists inside it are shared), copy vs view, and changing the set of keys while looping. A fifth trap is special to hash collections: a key that changes after insertion is lost. Step through each.

5. Choosing the right collection

The best structure is the one whose cheap operations match what your program does most. Complexities are for n elements on the native VM.

Rule of thumb: default to the literal ({}). Switch to SplayTreeMap/Set when you need sorted keys or "nearest key" queries; use HashMap only when you truly do not care about order and want to avoid the insertion-order bookkeeping; use a List when you need positions. Input size → feasible: a default map holds 10⁷ small entries comfortably (hundreds of MB); a duplicate check over n = 10⁵ with List.contains is 5·10⁹ steps, with a Set it is 10⁵.

Quiz

Interview questions

Cheat sheet: every member

Generated from the same member data as the cards above: every member with its cost and whether it mutates or returns something new.