Repository Guide | English | 한국어
Last Updated: 2026-10-20
Introduction to Algorithms, Cormen, Leiserson, Rivest, and Stein, Ch 11
Learning Objectives:
- Define a hash function, explain the goal of
$O(1)$ average-case search, insert, and delete, and explain why collisions are unavoidable using the pigeonhole principle- Compare separate chaining and open addressing as collision-resolution strategies, and distinguish linear probing, quadratic probing, and double hashing while explaining primary and secondary clustering
- Compute the load factor
$\alpha = n/m$ and analyze expected operation costs under the Simple Uniform Hashing Assumption (SUHA)- Describe rehashing and justify its amortized
$O(1)$ cost per insertion- Decide between a hash table and a balanced BST given workload requirements (ordered iteration, range queries, worst-case guarantees)
- Map the Set and Map abstractions to their hash-based implementations in real languages
- 1. Hashing Fundamentals
- 2. Collision Resolution
- 3. Performance Analysis
- 4. Sets, Maps, and Comparisons
- Summary
- Self-Check Questions
Hashing transforms data of arbitrary size into data of fixed size.
- Use a key to quickly look up a value.
- Store key-value pairs in a hash table.
- A hash function converts a key into an index that determines where data is stored.
Key ──► Hash Function ──► Hash Value (Index) ──► Hash Table
Figure 1. Flow from a key to the hash table
Goal: achieve
Note: Connection to Week 3. Week 3 gave us
$O(1)$ random access to an array slot if we already know the index. Hashing supplies the missing piece: a way to compute the index directly from the key, without searching for it.
A hash table is built from the three components in Table 1. Figure 2 shows its starting point, the direct-address table, which maps each key k of the universe U to slot k. Only the slots of the actual key set K = {2, 3, 5, 8} point to elements and the others stay empty, so memory is wasted when U is large. A hash function solves this by mapping keys to indices in a smaller table of size m.
Figure 2. Direct-address table storing key k in slot k
| Component | Role |
|---|---|
| Key | Unique identifier of each item |
| Hash function | Converts a key into a hash value (index) |
| Hash table | Array that stores the item at the computed index |
Table 1. Three components of a hash table
Key: "Alice" Hash Table
│ ┌───┬───────────┐
▼ │ 0 │ │
h("Alice") = 3 │ 1 │ │
│ │ 2 │ │
▼ │ 3 │ "Alice" │ ◄── stored here
Index = 3 │ 4 │ │
│ 5 │ │
└───┴───────────┘
Figure 3. Hash table storing the key Alice at index 3
A hash function
Division method (most common):
Example: table size
| Key |
Index | |
|---|---|---|
| 25 | 25 mod 10 | 5 |
| 37 | 37 mod 10 | 7 |
| 42 | 42 mod 10 | 2 |
| 55 | 55 mod 10 | 5 |
Table 2. Hash values of the division method with m = 10
Keys 25 and 55 both map to index 5; this is a collision.
Multiplication method (alternative):
- The value of
$m$ is not critical here (no prime-vs-power-of-2 trap). - Knuth suggests
$A \approx (\sqrt{5} - 1)/2 \approx 0.618$ (the golden ratio conjugate).
A well-designed hash function should satisfy:
- Deterministic: the same key always produces the same hash value.
- Uniform distribution: keys are spread evenly across the table.
-
Efficient: computed in
$O(1)$ time.
Choosing
- For the division method, avoid powers of 2:
$h(k) = k \bmod 2^p$ depends only on the lower$p$ bits of$k$ , so any structure in the high bits is thrown away. - A prime not close to a power of 2 is the standard recommendation (textbook Section 11.3).
Note: Why uniform matters. If every key hashes to the same slot, even the best collision-resolution scheme degenerates to a linked-list scan. The
$O(1)$ promise rests entirely on the assumption that the hash function spreads keys uniformly, which Section 2.2 formalizes as SUHA.
A collision occurs when two different keys produce the same hash value.
Figure 4. A hash function mapping keys to slots, with k2 and k5 colliding
Key: 25 ──► h(25) = 5 ──┐
├──► Index 5 (Collision!)
Key: 55 ──► h(55) = 5 ──┘
Figure 5. Keys 25 and 55 colliding at index 5
Pigeonhole principle: the key space is generally much larger than the index space (
Even with
The practical question is therefore not how to avoid collisions but how to resolve them efficiently. Table 3 lists the two main families.
| Strategy | Also Known As | Idea |
|---|---|---|
| Separate Chaining | Open Hashing | Linked list of colliding elements |
| Open Addressing | Closed Hashing | Find another empty slot |
Table 3. Two strategies for collision resolution
Each table slot holds a linked list of all key-value pairs that hash to that index.
Figure 6. Separate chaining resolving collisions with linked lists
Hash Table
┌───┬──────────────────────────────┐
│ 0 │ → NULL │
│ 1 │ → [11] → [21] → NULL │
│ 2 │ → [42] → NULL │
│ 3 │ → [13] → [33] → [73] → NULL │
│ 4 │ → NULL │
│ 5 │ → [25] → [55] → NULL │
│ 6 │ → NULL │
│ 7 │ → [37] → NULL │
│ 8 │ → NULL │
│ 9 │ → [19] → NULL │
└───┴──────────────────────────────┘
Figure 7. Separate-chaining hash table with h(k) = k mod 10
Operations:
| Operation | Procedure | Cost |
|---|---|---|
Insert(k) |
Compute |
|
Search(k) |
Compute |
|
Delete(k) |
Search for |
Table 4. Operations and costs of separate chaining
Simple Uniform Hashing Assumption (SUHA): any key is equally likely to hash to any of the
Define the load factor as
Under SUHA the expected length of each chain is exactly
[Probability and Statistics] This value follows directly from indicator random variables and linearity of expectation, taught in Probability and Statistics. Fix one slot and let
$X_i$ be 1 if key$i$ hashes to that slot and 0 otherwise; SUHA gives$E[X_i] = 1/m$ , and since the chain length is$X_1 + \cdots + X_n$ , its expectation is$n/m = \alpha$ .
| Operation | Average Case | Worst Case |
|---|---|---|
| Search (unsuccessful) | ||
| Search (successful) | ||
| Insert | ||
| Delete |
Table 5. Average and worst-case complexity of separate chaining operations
If we keep
Note: Worst case. All
$n$ keys hash to the same slot. The table degenerates into one long linked list and search costs$\Theta(n)$ . This is why a sound hash function (and rehashing, Section 3.2) is critical.
All elements are stored directly in the table, with no linked lists. When a collision occurs, the algorithm probes for the next available slot.
General probe sequence:
Three standard probing strategies:
| Method | Idea | Formula |
|---|---|---|
| Linear Probing | Check consecutive slots | |
| Quadratic Probing | Check with quadratic gaps | |
| Double Hashing | Use a second hash function for the step |
Table 6. Three probing strategies of open addressing
Here
Because all entries live in one contiguous array (no per-element nodes), open addressing avoids the pointer-chasing that makes separate chaining cache-unfriendly. Linear probing in particular walks adjacent memory, so consecutive slots usually share a cache line and it benefits strongly from memory locality. This is why open addressing is described as cache-friendly.
Caution: Deletion needs care. Naively clearing a slot breaks probe chains: search stops at the first empty slot, so any key placed after the cleared slot via probing becomes unreachable. Deleted slots are therefore marked with a tombstone (a deletion marker): search keeps probing past it, while insert may reuse it (revisited in Self-Check Question 10).
Insert keys
Step 1: Insert 25 → h(25)=5 Step 2: Insert 37 → h(37)=7
┌───┬────┐ ┌───┬────┐
│ 5 │ 25 │ │ 5 │ 25 │
│ 7 │ │ │ 7 │ 37 │
└───┴────┘ └───┴────┘
Step 3: Insert 42 → h(42)=2 Step 4: Insert 55 → h(55)=5
┌───┬────┐ ┌───┬────┐
│ 2 │ 42 │ │ 2 │ 42 │
│ 5 │ 25 │ │ 5 │ 25 │ ← occupied!
│ 7 │ 37 │ │ 6 │ 55 │ ← probe to 6
└───┴────┘ │ 7 │ 37 │
└───┴────┘
Step 5: Insert 73 → h(73)=3
┌───┬────┐
│ 2 │ 42 │
│ 3 │ 73 │
│ 5 │ 25 │
│ 6 │ 55 │
│ 7 │ 37 │
└───┴────┘
Figure 8. Inserting 25, 37, 42, 55, 73 by linear probing
Primary clustering in linear probing:
- Occupied slots tend to form long contiguous blocks.
- A new key that hashes anywhere into a cluster must probe to the end of it.
- Clusters absorb new keys faster than empty regions, so they grow super-linearly and worsen performance.
┌───┬────┐
│ 0 │ │
│ 1 │ │
│ 2 │ 42 │ ┐
│ 3 │ 73 │ │ cluster
│ 4 │ ?? │ │ (growing)
│ 5 │ 25 │ │
│ 6 │ 55 │ │
│ 7 │ 37 │ ┘
│ 8 │ │
│ 9 │ │
└───┴────┘
Figure 9. A growing primary cluster in linear probing
Note: Figure 9 shows the table of Section 2.4 after one more key lands in the empty slot 4. In the state of Section 2.4, slots 2-3 and slots 5-7 are separate clusters, and filling slot 4 merges them into one cluster spanning slots 2-7.
- Quadratic probing reduces primary clustering but introduces secondary clustering: keys with the same initial hash still follow identical probe sequences.
- Double hashing produces the best distribution and nearly eliminates clustering.
Quadratic-probing trace: take
| Slot | Result | ||
|---|---|---|---|
| 0 | 3 | occupied → next | |
| 1 | 4 | occupied → next | |
| 2 | 7 | occupied → next | |
| 3 | 1 | empty → place here |
Table 7. Quadratic-probing insertion of a key starting at slot 3
The gaps
Note: Intuition. Clustering is what happens when probe paths are correlated. Linear probing makes every nearby key share a path; double hashing decorrelates probe sequences by using a per-key step size.
Double hashing uses two hash functions:
-
$h_1(k)$ chooses the initial slot. -
$h_2(k)$ chooses the step size between probes.
Requirements:
-
$h_2(k) \neq 0$ for every key$k$ (otherwise we loop in place). -
$h_2(k)$ should be relatively prime to$m$ so the probe sequence visits every slot before repeating.
A standard recipe: pick
Example:
| Key |
Probe sequence | ||
|---|---|---|---|
| 15 | 1 | 1, 2, 3, 4, 5, 6, 0 | |
| 22 | 1 | 1, 4, 0, 3, 6, 2, 5 |
Table 8. Probe sequences of double hashing with m = 7
The two keys collide at index 1 but follow different probe paths from there.
Figure 10 inserts the key 14 into a table with
Figure 10. Inserting key 14 by double hashing
The load factor is
|
|
Meaning | Performance |
|---|---|---|
| Table mostly empty | Excellent, close to |
|
| Moderately full | Good, acceptable | |
| Crowded | Degraded, more collisions | |
| Full (open addressing) | Very poor, long probe runs | |
| Only possible with chaining | Chains become long |
Table 9. Meaning and performance by load factor range
Rule of thumb:
- Separate chaining: keep
$\alpha \leq 1.0$ . - Open addressing: keep
$\alpha \leq 0.7$ (resize before this threshold).
Note: Why open addressing is more sensitive. With chaining, a high
$\alpha$ just means longer chains. With open addressing, as$\alpha \to 1$ the expected probe length under uniform hashing grows like$\dfrac{1}{1-\alpha}$ , which blows up rapidly.
When the load factor crosses a threshold, rehash, i.e., resize the table:
- Allocate a new table of size
$m' \approx 2m$ (typically the next prime after$2m$ ). -
Recompute
$h(k)$ for every existing key using the new table size. - Reinsert all elements into the new table.
- Free the old table.
Old table (m=5, n=4, α=0.8) New table (m=11, n=4, α≈0.36)
┌───┬────┐ ┌────┬────┐
│ 0 │ 25 │ rehash │ 0 │ 11 │
│ 1 │ 11 │ ─────────► │ 1 │ │
│ 2 │ 42 │ │ 2 │ │
│ 3 │ 73 │ │ 3 │ 25 │
│ 4 │ │ │ 4 │ │
└───┴────┘ │ 5 │ │
│ 6 │ │
│ 7 │ 73 │
│ 8 │ │
│ 9 │ 42 │
│ 10 │ │
└────┴────┘
Figure 11. Rehashing a table of size 5 into a table of size 11
Cost: one rehash is
Note: Connection to Week 2. This is the same doubling argument used by the dynamic array that Week 2 gave as its example of amortized analysis, such as the C++
std::vectorand Pythonlistforpush_back/append. The dynamic-array amortization is exactly the trick that lets a hash table claim$O(1)$ insertion in spite of occasional$O(n)$ rebuilds.
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | ||
| Insert |
|
|
| Delete |
Table 10. Average and worst-case complexity of hash table operations
Why
- Under SUHA the expected chain (or probe) length is
$\Theta(1 + \alpha)$ . - Rehashing keeps
$\alpha = O(1)$ , so each operation costs$O(1)$ .
When does the
- A poorly chosen hash function that maps too many keys to the same slot.
- An adversarial input crafted to exploit a known hash function. This is a real concern in web servers (hash-flooding DoS attacks), so many languages now randomize their hash seed at startup.
Note: A wishful assumption. A hash table can be seen as a finite map plus a wishful assumption that collisions are rare.
Hash tables power two of the most ubiquitous abstractions in programming:
Set is a collection of unique elements (no duplicates).
- Operations
add(x),contains(x), andremove(x)are all$O(1)$ on average. - Examples: Python
set(), JavaHashSet, C++unordered_set.
Map (Dictionary) is a collection of key-value pairs.
- Operations
put(k, v),get(k), andremove(k)are all$O(1)$ on average. - Examples: Python
dict, JavaHashMap, C++unordered_map.
# Python Set example # Python Dict (Map) example
visited = set() phone = {}
visited.add("A") phone["Alice"] = "010-1234"
visited.add("B") phone["Bob"] = "010-5678"
visited.add("A") # duplicate! print(phone["Alice"]) # O(1)
print(len(visited)) # 2 print("Bob" in phone) # O(1)
print("A" in visited) # True, O(1)These are among the most heavily used data structures in coding interviews and competitive programming, and many algorithmic problems reduce to choosing the right Set or Map.
| Criterion | Hash Table | Balanced BST (e.g., RBT in Week 9) |
|---|---|---|
| Average search | ||
| Worst-case search |
|
|
| Ordered iteration | Not supported (or |
|
| Range queries | Not supported |
|
| Memory overhead | Array + chains/probes | Pointers per node |
| Implementation | Needs a good hash function | Self-balancing logic |
Table 11. Comparison of a hash table and a balanced BST
Use a hash table when:
- You only need lookup, insert, and delete by exact key.
- Average-case
$O(1)$ matters more than worst-case guarantees.
Use a balanced BST when:
- You need ordered traversal, range queries, or min/max.
- A worst-case
$O(\log n)$ guarantee is required (e.g., real-time systems).
Note: Tying it back to Week 9. RBTs and B-Trees enforce order. Hash tables throw order away in exchange for direct addressing. The cost model, that is, whether order matters, picks the structure.
| Concept | Key Summary |
|---|---|
| Hash function | Hashing turns lookup into arithmetic: the hash function maps a key to an index in |
| Collisions | Collisions are unavoidable by the pigeonhole principle, so the real question is the resolution strategy. |
| Separate chaining | It keeps a linked list per slot, costs |
| Open addressing | It probes for the next free slot by linear probing, quadratic probing, or double hashing, and under uniform hashing an unsuccessful search takes at most |
| Clustering | It is the main failure mode of probing schemes, and double hashing largely fixes it by decorrelating probe sequences. |
| Load factor |
|
| Rehashing | The table doubles when |
| Average and worst case | The |
| Set and Map | They are hash-backed abstractions for asking whether an element is present and which value a key maps to, running in |
| Hash tables and balanced BSTs | They are complementary, not interchangeable, and the choice depends on whether the workload needs order. |
-
Division method: Why is choosing
$m = 2^p$ usually a bad idea for$h(k) = k \bmod m$ ? Construct a key set that exposes the weakness.Answer
$k \bmod 2^p$ depends only on the lower$p$ bits of$k$ , so any structure in the higher bits is thrown away. If keys share a common low-bit pattern they all collide into a tiny subset of slots. Example with$m = 8$ : keys${8, 16, 24, 32, 40, 48, \ldots}$ are all$\equiv 0 \pmod 8$ , so every key collides at slot 0 regardless of how many slots remain. A prime$m$ not close to a power of 2 mixes high and low bits and avoids this trap (textbook Section 11.3). -
Pigeonhole / Birthday: Suppose
$m = 365$ and we insert random keys one at a time. How many insertions before the probability of some collision exceeds 1/2? Why is this much smaller than$m$ ?Answer
The classic birthday paradox answer is
$n \approx 23$ , far smaller than$m = 365$ . The reason is combinatorial: with$n$ insertions there are$\binom{n}{2} \approx n^2/2$ pairs of keys, and each pair collides with probability$1/m$ . The probability of no collision is therefore about$e^{-n^2/(2m)}$ , which drops to 1/2 around$n \approx \sqrt{2m \ln 2} \approx 1.18\sqrt{m}$ (the expected number of collisions reaches 1 around$n \approx \sqrt{2m}$ ). The 1/2-probability threshold scales as$\Theta(\sqrt{m})$ , not$\Theta(m)$ , so collisions arise much earlier than naive intuition suggests. -
Chaining complexity: A chained hash table holds
$n = 10^6$ keys in$m = 250{,}000$ slots. Under SUHA, what is the expected time for an unsuccessful search? For a successful one?Answer
Load factor
$\alpha = n/m = 10^6 / 250{,}000 = 4$ . Under SUHA, expected chain length equals$\alpha$ , so an unsuccessful search scans an entire chain on average, taking about$1 + \alpha = 5$ steps (compute the hash plus 4 list-node visits). A successful search scans about half the chain it lands in, taking about$1 + \alpha/2 = 3$ steps. Both are$\Theta(1 + \alpha)$ , hence$O(1)$ when$\alpha$ is constant, but the constant is noticeable, so typically$\alpha \leq 1$ is preferred. -
Linear probing trace: Insert
${4, 14, 24, 25, 35}$ into a table of size$m = 10$ with$h(k) = k \bmod 10$ using linear probing. Draw the final table and report the probe count for each insertion.Answer
$h(4) = 4$ → place at slot 4 (1 probe).$h(14) = 4$ → slot 4 taken, try 5 → place at slot 5 (2 probes).$h(24) = 4$ → 4,5 taken, try 6 → place at slot 6 (3 probes).$h(25) = 5$ → 5,6 taken, try 7 → place at slot 7 (3 probes).$h(35) = 5$ → 5,6,7 taken, try 8 → place at slot 8 (4 probes). Final: slot 4=4, 5=14, 6=24, 7=25, 8=35. A single primary cluster of length 5 forms, demonstrating clustering. -
Double hashing path: With
$m = 11$ ,$h_1(k) = k \bmod 11$ ,$h_2(k) = 1 + (k \bmod 9)$ , list the first four probe positions for the keys$k = 22$ and$k = 33$ . Do they ever revisit the same slot?Answer
For
$k = 22$ :$h_1 = 0$ ,$h_2 = 1 + 4 = 5$ → probes 0, 5, 10, 4 (each step+5 mod 11). For$k = 33$ :$h_1 = 0$ ,$h_2 = 1 + 6 = 7$ → probes 0, 7, 3, 10. They collide at slot 0 initially and revisit slot 10 at different probe indices ($i=2$ for 22,$i=3$ for 33), but their full probe sequences are otherwise different: the two step sizes (5 and 7) decorrelate the paths after the initial collision, which is exactly what eliminates clustering. -
Load factor and probe length: Derive (or look up) the expected number of probes for an unsuccessful search under uniform hashing with open addressing:
$E[\text{probes}] \leq \dfrac{1}{1-\alpha}$ . What happens as$\alpha \to 1$ ? What does this imply about resize thresholds?Answer
Under uniform hashing, the first probe finds an occupied slot with probability
$\alpha = n/m$ . Conditioning on that, the second probe is occupied with probability$\approx (n-1)/(m-1) \leq \alpha$ , and so on. The expected probe count is bounded by$\sum_{i \geq 0} \alpha^i = \dfrac{1}{1 - \alpha}$ (geometric series). As$\alpha \to 1$ this diverges to infinity: at$\alpha = 0.9$ expected probes is 10, at$\alpha = 0.99$ it is 100. Practical rule: resize before$\alpha \approx 0.7$ for open addressing to keep expected probes at most about 3.3. -
Rehashing amortization: Show that if we double the table whenever
$\alpha > 0.75$ , the total cost of$n$ insertions is$O(n)$ . State the implicit amortized argument explicitly.Answer
Rehashes occur at sizes roughly
$m_0, 2m_0, 4m_0, \ldots$ , each costing$\Theta(m_i)$ to reinsert all keys. Total rehash cost is$\Theta(m_0 + 2m_0 + 4m_0 + \cdots + n) = \Theta(2n) = O(n)$ , a geometric series dominated by its last term. Combined with$n$ trivial$O(1)$ insertions, total work is$O(n)$ , giving amortized$O(1)$ per insertion. The accounting argument: charge each insertion$O(1)$ extra credit; when the table doubles, the accumulated credit pays for the bulk reinsertion. Same trick used bystd::vector::push_backand Pythonlist.append. -
Hash table vs BST: For each workload below, choose between a hash table and a balanced BST, and justify in one sentence. (a) A spell-checker that asks whether a word is in the dictionary. (b) An autocomplete service that returns all words starting with a given prefix. (c) A leaderboard that must always be iterable in score order. (d) A real-time controller that requires
$O(\log n)$ worst-case lookup.Answer
(a) Hash table: Only exact-match membership is queried, so average
$O(1)$ lookup is best. (b) BST (or trie): Prefix queries require ordered traversal, which hash tables do not support efficiently. (c) BST: In-order iteration must yield scores in order. (d) BST (RBT): Real-time systems require worst-case$O(\log n)$ , while hash tables can degrade to$O(n)$ on bad inputs. -
Adversarial inputs: A web framework hashes user-supplied strings into a fixed table. Explain how an attacker could degrade performance to
$O(n)$ per request, and how randomized (seeded) hashing mitigates the attack.Answer
If the hash function is deterministic and public (e.g., a fixed seed), an attacker can pre-compute many strings that hash to the same slot and submit them as POST parameters. All keys land in one chain, turning each insertion into
$O(n)$ list traversal, an attack known as hash-flooding DoS (PHP, Java, Python were all vulnerable c. 2011). Randomized hashing chooses a secret seed at process startup, so the attacker cannot precompute colliders for a specific server; SipHash with a random key is the modern standard adopted by Python, Ruby, and Rust. -
Open addressing deletion: Why is naively clearing a slot dangerous in open addressing, and how is the tombstone (deletion marker) trick used to preserve probe-chain correctness?
Answer
Open addressing's search rule stops at the first empty slot, assuming that if the key existed it would have been placed earlier in the probe sequence. If you clear a slot in the middle of a probe chain, any key inserted after it via probing becomes unreachable; search terminates at the gap before finding it. The tombstone trick marks the slot as deleted but previously occupied: search treats it as occupied (keep probing), while insert treats it as empty (may reuse). Tombstones accumulate over time, so periodic rehashing is needed to flush them.