Lesson 04 of 16 · 25:51
Hash tables
A hash table trades extra memory for fast lookup. A hash function turns a key into a number, the table chooses a bucket, and collision handling distinguishes keys that land together. The useful interview abstraction is a map or set, but understanding buckets explains why performance is average-case rather than magic.
Hashing often changes the question from “search everything seen so far” to “ask one direct question about what has been seen.” The central design decision is what the key means and what fact the value should store.
What you should be able to do after this lesson
- Choose keys that represent the needed lookup
- Distinguish sets from key/value maps
- Explain collision and load assumptions honestly
The mental model
Hash the key into a bucket, then resolve any collision inside that bucket. Speed comes from keeping each bucket’s candidate set small.
Recognize it when: Reach for hashing when the prompt asks about membership, deduplication, frequencies, grouping, complements, memoization, or a direct key-to-record association.
The invariant to say aloud: The table summarizes exactly the keys processed so far, and each stored value has a precise meaning such as count, earliest index, or canonical group.
Learn the ideas one at a time
Concept 1 of 4
Hash function
Watch from 0:00 ↗A deterministic function turns a hashable key into an integer; the table maps that integer into a finite bucket range. Equal keys must hash compatibly.
A valid hash is deterministic during the table's use, and equal keys must produce compatible hashes. The integer hash is compressed into a finite bucket range. Objects used as keys therefore need stable equality and hashing behavior; mutable contents make that stability difficult.
Walk through an example
If bucket = hash(key) mod 8, two different keys may both select bucket 3. The bucket location narrows the search; equality still confirms which key was requested.
In an interview
Explain the semantic key, not just the container: for two-sum, the key is a value already seen and the lookup asks whether target - current exists.
Concept 2 of 4
Collisions
Watch from 0:00 ↗Different keys can land in the same bucket. Chaining or open addressing preserves correctness; collision handling is not optional.
A collision is expected whenever many possible keys map into fewer buckets. Chaining stores multiple entries per bucket; open addressing probes for another slot. Both preserve correctness by checking key equality, while a poor distribution increases the work needed inside the chosen bucket or probe sequence.
Walk through an example
Keys A and B land in bucket 5. Looking up B first selects bucket 5, rejects A after an equality check, and then finds B. Without collision handling, inserting B would incorrectly destroy A.
In an interview
Use “average O(1)” for lookup and acknowledge that concentrated collisions can approach O(n).
Concept 3 of 4
Sets and maps
Watch from 0:00 ↗A set stores keys for membership. A map stores key/value associations. Both commonly provide average O(1) insert, lookup, and delete.
A set answers whether a key exists. A map associates a key with a value such as a count, index, parent, or best score. Decide what future question you need to answer; that question usually tells you whether existence alone is enough or whether metadata must be stored.
Walk through an example
For [2, 7, 11] with target 9, at 2 the complement 7 is absent, so store 2. At 7 the complement 2 exists, so the pair is found without rescanning the prefix.
In an interview
Define the meaning of the table in one sentence—for example, “seen maps each value to its earliest index.” That sentence becomes your invariant.
Concept 4 of 4
Load and worst case
Watch from 0:00 ↗As occupancy grows, resize/rehash keeps buckets sparse. Pathological collisions can degrade an operation toward O(n), so say average-case O(1), not guaranteed O(1).
As the number of entries approaches the number of buckets, collisions become more common. Implementations resize and redistribute entries to keep the load factor controlled. A resize can cost O(n), but, like dynamic arrays, occasional resizing is amortized over many ordinary operations.
Walk through an example
A table doubles after crossing a load threshold. One insertion rehashes all entries, while the next many insertions use the new spare capacity. The sequence remains efficient even though that single operation was expensive.
In an interview
Mention memory O(n), average O(1) operations, and a possible O(n) worst case when the analysis needs to be precise.
Before you call this lesson done
- State what each key and value means
- Check before or after insertion in the correct order
- Account for duplicates
- Give average-case and worst-case complexity accurately
