Map + set: create / insert / “have I seen X?” / delete / iterate. All operations average O(1); iteration is O(n). Worst case is O(n) under pathological collisions — ignore that in interviews unless asked.
dict / sethash map (dict) | hash set (set) | |
|---|---|---|
| create | m = {} | s = set() |
| insert | m[k] = v | s.add(x) |
| seen X? | k in m | x in s |
| delete | del m[k] / m.pop(k, None) | s.discard(x) |
| iterate | for k, v in m.items(): | for x in s: |
{} is an empty dict, never an empty set — you must write set().m[k] on a missing key raises KeyError; use m.get(k, default) to probe safely.list can't be a key — convert to tuple first.map[K]V / map[T]struct{}| hash map | hash set (idiom) | |
|---|---|---|
| create | m := map[string]int{} | s := map[string]struct{}{} |
| insert | m[k] = v | s[x] = struct{}{} |
| seen X? | _, ok := m[k] | _, ok := s[x] |
| delete | delete(m, k) | delete(s, x) |
| iterate | for k, v := range m {} | for x := range s {} |
0, "") silently — use the , ok form to distinguish “absent” from “stored zero”.nil map (declared, not made) panics on write; create with make or a literal.Map / Sethash map (Map) | hash set (Set) | |
|---|---|---|
| create | const m = new Map<string, number>() | const s = new Set<number>() |
| insert | m.set(k, v) | s.add(x) |
| seen X? | m.has(k) | s.has(x) |
| delete | m.delete(k) | s.delete(x) |
| iterate | for (const [k, v] of m) {} | for (const x of s) {} |
{}) stringify their keys — obj[1] and obj["1"] collide. Prefer Map/Set.Map/Set compare keys by identity for objects: two equal-looking arrays are two different keys.m.size, a property — not m.length, not m.size().unordered_map / unordered_set| hash map | hash set | |
|---|---|---|
| create | unordered_map<string, int> m; | unordered_set<int> s; |
| insert | m[k] = v; | s.insert(x); |
| seen X? | m.count(k) / m.contains(k) | s.count(x) / s.contains(x) |
| delete | m.erase(k); | s.erase(x); |
| iterate | for (auto& [k, v] : m) {} | for (auto& x : s) {} |
m[k] on a missing key default-constructs and inserts it — probing with [] silently grows the map. Ask with count/contains (C++20) instead.std::pair/std::vector keys need a custom hash; there is no default.map/set (no unordered_) are trees: sorted order, but O(log n) per operation.