-
Notifications
You must be signed in to change notification settings - Fork 0
003 — Hash Maps and Hash Sets
If arrays are "I know exactly where to look because I have the index," hash maps are "I know exactly where to look because a formula tells me" — even though you never assigned that spot yourself.
Picture a coat check counter at a theater. You hand over your coat, and instead of the attendant scanning every peg on the wall, they run your ticket number through a rule — say, "peg number = ticket number mod 100" — and hang your coat on that exact peg. Later, you hand back your ticket, they run the same rule, and walk straight to the peg. No searching the whole wall.
- 🎟️ The ticket number is your key.
- 🧥 The coat is your value.
- 🧮 The rule ("mod 100") is the hash function — it turns a key into a peg number (a bucket index).
Now imagine two different ticket numbers both hash to peg 37. That's a collision. The attendant doesn't panic — they just hang both coats on the same peg, one in front of the other, and when you come back, they check tags until they find yours. Rare, but the system needs a plan for it.
A hash map (Swift: Dictionary) stores key-value pairs. A hash set (Swift: Set) is the same idea with just keys, no values — it only answers "is this in the collection?"
Under the hood, both are built on a hash table: an array of buckets, where a key's hash function determines which bucket it lands in. Looking something up means: hash the key → jump straight to that bucket → (rarely) check a short list for collisions. That's what makes lookup, insert, and delete average O(1) — no scanning the whole collection like you would with an array.
In Swift, any type conforming to Hashable (most stdlib types already do, and you get it free via Codable-style synthesis for your own structs/enums with all-Hashable members) can be a dictionary key or set element.
Reach for a hash map when:
- You need to look something up by a key, fast, and don't care about order (
Dictionaryis unordered). - You're counting frequencies ("how many times does each character appear?").
- You're grouping items by some computed property.
- You need "have I seen this before?" with
O(1)checks instead ofO(n)array scans.
Reach for a hash set when:
- You just need membership testing or deduplication — no associated value.
- You need fast set algebra: union, intersection, subtraction.
Skip it when: you need ordering preserved, or you need range queries ("give me everything between X and Y") — a hash table gives you neither; reach for a sorted structure instead.
buckets (array of size 8):
index: 0 1 2 3 4 5 6 7
┌───┐ ┌───────┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐ ┌───┐
│nil│ │"cat"→3│ │nil│ │nil│ │nil│ │nil│ │nil│ │nil│
└───┘ │"bat"→7│ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘
└───────┘
▲
collision! hash("cat") % 8 == hash("bat") % 8 == 1
both live in bucket 1 as a small chained list
lookup("cat"):
1. hash("cat") → some big number
2. big number % 8 → bucket 1
3. walk the short chain in bucket 1, compare keys → found "cat" → 3
// Dictionary
var wordCount: [String: Int] = [:]
for word in ["cat", "bat", "cat", "cat"] {
wordCount[word, default: 0] += 1 // O(1) average lookup + write
}
print(wordCount) // ["cat": 3, "bat": 1]
let value = wordCount["cat"] // O(1) average, returns Int?
wordCount.removeValue(forKey: "bat") // O(1) average
// Grouping — a very common interview move
let words = ["eat", "tea", "tan", "ate", "nat", "bat"]
let grouped = Dictionary(grouping: words) { String($0.sorted()) }
// ["aet": ["eat", "tea", "ate"], "ant": ["tan", "nat"], "abt": ["bat"]]
// Set
var seen: Set<Int> = []
let hasDuplicate = [1, 2, 3, 2].contains { !seen.insert($0).inserted } // O(1) avg per insert
let a: Set = [1, 2, 3]
let b: Set = [2, 3, 4]
a.intersection(b) // [2, 3]
a.union(b) // [1, 2, 3, 4]
a.subtracting(b) // [1]struct SimpleHashMap<Key: Hashable, Value> {
private var buckets: [[(key: Key, value: Value)]]
private var capacity: Int
init(capacity: Int = 16) {
self.capacity = capacity
self.buckets = Array(repeating: [], count: capacity)
}
private func bucketIndex(for key: Key) -> Int {
// Never use raw hashValue for real code (it's not stable across
// launches) — but it's fine to illustrate the mechanism.
return abs(key.hashValue) % capacity
}
mutating func set(_ key: Key, _ value: Value) {
let index = bucketIndex(for: key)
if let existingIndex = buckets[index].firstIndex(where: { $0.key == key }) {
buckets[index][existingIndex].value = value // overwrite
} else {
buckets[index].append((key, value)) // new entry, chain it
}
}
func get(_ key: Key) -> Value? {
let index = bucketIndex(for: key)
return buckets[index].first(where: { $0.key == key })?.value
}
mutating func remove(_ key: Key) {
let index = bucketIndex(for: key)
buckets[index].removeAll { $0.key == key }
}
}
// Note: firstIndex(where:) requires Key to also be Equatable,
// which Hashable already guarantees.| Operation | Big-O | Why |
|---|---|---|
Insert (map[key] = value) |
O(1) average |
Hash the key, jump straight to its bucket. See Big-O Notation. |
Lookup (map[key]) |
O(1) average |
Same jump — no scanning other buckets. |
Delete (removeValue(forKey:)) |
O(1) average |
Find the bucket, remove from its (usually tiny) chain. |
| Insert / lookup, worst case | O(n) |
If every key collides into the same bucket (a poor hash function, or an adversarial input), you degrade to scanning a single long chain — linear, like an array. |
| Iterate all entries | O(n) |
Must visit every bucket and every chained entry once. |
| Set union / intersection | O(n + m) |
Walk both sets once each, checking membership as you go. |
A hash map is a coat check counter with a magic formula — it computes exactly which peg your coat is on, instead of scanning the whole wall.
Suppose two different strings, "abc" and "xyz", happen to hash to the same bucket in the SimpleHashMap above. Walk through what set("abc", 1) followed by set("xyz", 2) followed by get("abc") actually does inside the bucket's array, and explain why the collision doesn't cause "abc"'s value to be lost or overwritten.