Sets, maps and the abstract data type view
Separating the interface from the implementation, ordered versus unordered iteration, the guarantees each container actually makes, and how to read a standard library's naming.
The interface is the contract
An abstract data type is defined by the operations it promises and the guarantees attached to them — not by the code underneath. A map is "keys to values with lookup, insert and remove"; a hash table and a balanced tree are two implementations with different guarantees.
| ADT | Core operations | Typical implementations |
|---|---|---|
| List | append, insert, get, remove at index | Dynamic array, linked list |
| Stack | push, pop, peek | Array or linked list |
| Queue | enqueue, dequeue | Ring buffer, linked list |
| Map / dictionary | get, put, delete, containsKey | Hash table, balanced tree |
| Set | add, remove, contains, union, intersect | Hash set, tree set, bitset |
| Priority queue | insert, find-min, extract-min | Binary heap, pairing heap |
| Graph | neighbours, addEdge | Adjacency list, matrix |
Choosing an ADT first and an implementation second is the whole discipline. Most accidental complexity in application code comes from picking a concrete structure before deciding which operations must be fast.
Ordered or not — the decision that changes everything
- An unordered map (hash map) offers expected O(1) lookup and no order guarantee.
- An ordered map (balanced tree) offers O(log n) and sorted iteration, plus range queries and predecessor/successor.
- A insertion-ordered map preserves the order keys were added, which is a third behaviour entirely.
- Iteration order in a hash map can change when the table resizes, so code that depends on it breaks after a deployment.
from collections import OrderedDict
d = {"b": 2, "a": 1} # dict preserves insertion order (3.7+)
sorted_items = sorted(d.items()) # explicit sort when you need key order
# Python's dict is insertion-ordered; many languages' maps are not.
# Rust: HashMap unordered, BTreeMap ordered
# Java: HashMap unordered, LinkedHashMap insertion, TreeMap sorted
# JavaScript: Map insertion-ordered, plain object mostly soMap<String, Integer> hash = new HashMap<>(); // O(1) expected, no order
Map<String, Integer> ins = new LinkedHashMap<>(); // insertion order
Map<String, Integer> sorted = new TreeMap<>(); // sorted by key, O(log n)
// range queries only exist on the sorted implementation
SortedMap<String, Integer> tail = ((TreeMap<String, Integer>) sorted).tailMap("m");Sets, and the cost of what they promise
| Operation | Hash set | Tree set | Sorted array |
|---|---|---|---|
| contains | O(1) expected | O(log n) | O(log n) |
| add | O(1) expected | O(log n) | O(n) to shift |
| union of two | O(n + m) | O(n + m) with merging | O(n + m) |
| smallest element | O(n) scan | O(log n) | O(1) |
| ordered iteration | Sort first: O(n log n) | O(n) | O(n) |
seen = set()
for row in stream:
key = (row["tenant"], row["id"])
if key in seen: # O(1) expected
continue
seen.add(key)FAQ
Do I need an ordered map?
Why is a Python dict ordered but a Java HashMap not?
Related
Amortised analysis: what operations really cost Tries and prefix trees
Last refreshed 2026-09-18.