Hash tables, hash functions, load factor; separate chaining

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Lower bound for comparison-based search? from Lesson 2.1.2
• Binary search probes on 1,000 elements (max)? from Lesson 2.1.1
• Amortised cost of appending to a doubling array? from Lesson 1.3.1

1 · The Hook

🎣

A compiler looks up every variable name in a symbol table, millions of times. Even log n comparisons per lookup is too slow. Hashing computes a slot number directly from the key, so a lookup usually touches one or two slots: expected O(1). The price: collisions, and the work to resolve them.

2 · Predict First

🤔

A table has 7 slots; h(k) = k mod 7. Keys 15, 11, 27, 8, 12, 19, 23, 40 arrive in that order, and each slot holds a linked list of keys (chaining). Which slot gets the longest list?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

15 → 1, 11 → 4, 27 → 6, 8 → 1, 12 → 5, 19 → 5, 23 → 2, 40 → 5. Slot 5 holds 12, 19, 40 (3 keys).

Hash table and hash function

• A table of m slots; a hash function h maps a key to a slot 0 … m − 1.
• Division method: h(k) = k mod m. Choose m a prime not close to a power of 2.
• Multiplication method: h(k) = ⌊m · frac(k·A)⌋ with 0 < A < 1 (Knuth: A ≈ 0.618). m can be a power of 2.
• Collision: two keys with the same slot. With more keys than slots, collisions are unavoidable (pigeonhole), and usually happen much earlier.

Load factor

α = n / m (keys stored ÷ slots). It decides the expected cost.

Separate chaining

Each slot points to a linked list of the keys hashing there.

• Insert: put at the head of the list: O(1).

• Search: hash, then scan that list.

• Under simple uniform hashing (every key equally likely in any slot, independently):

• unsuccessful search examines α keys on average (expected time Θ(1 + α));

• successful search examines about 1 + α/2 keys.

• Worst case: all keys in one list: Θ(n).

• α may exceed 1.

Why O(1)?

If m grows with n so that α stays bounded (say α ≤ 1), every operation is expected Θ(1).

4 · Visual

m = 7, h(k) = k mod 7, chaining (keys added at the tail here, to show arrival order)

slot 0: -
slot 1: 15 -> 8
slot 2: 23
slot 3: -
slot 4: 11
slot 5: 12 -> 19 -> 40
slot 6: 27
                    n = 8 keys, alpha = 8/7

5 · Worked Examples

Example 1 Easy

A chained table has 100 slots and 250 keys. Load factor?

Solution

α = 250/100 = 2.5.

Example 2 Medium

In the predict table, how many keys are examined by an unsuccessful search for a key hashing to slot 5?

Solution

All 3 keys in slot 5's list.

Example 3 GATE

Simple uniform hashing, chaining, 1,000 slots, 3,000 keys. Expected number of keys examined in an unsuccessful search?

Solution

α = 3.

6 · GATE Traps

⚠️

• α = n/m can be greater than 1 with chaining, never with open addressing.
• Expected O(1) needs simple uniform hashing and bounded α; the worst case is Θ(n).
• Division method: avoid m = 2ᵖ (only low bits of k matter).
• Count keys examined, not slots, when comparing chaining costs.

7 · Memory Hook

🧠

"Hash to a slot, walk its chain; α is the average chain."

8 · Connect the Dots

Chaining keeps colliding keys outside the table. Next: open addressing keeps everything inside the table and probes for the next free slot: linear, quadratic and double hashing.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markLoad factor

A chained table with 64 slots stores 96 keys. α = ?

Numerical answer: ________

Q2NAT2 marksChain length

m = 7, h(k) = k mod 7, chaining. Keys 15, 11, 27, 8, 12, 19, 23, 40. How many slots are empty?

Numerical answer: ________

Q3MCQ1 markChaining cost

With chaining and simple uniform hashing, an unsuccessful search takes expected time:

• (A) Θ(1 + α)
• (B) Θ(1)
• (C) Θ(log n)
• (D) Θ(n)

Q4NAT1 markDivision hash

h(k) = k mod 13. Which slot does 100 go to?

Numerical answer: ________

Q5MSQ2 marksFacts

Which are true for separate chaining?

• (A) It needs a second hash function.
• (B) The load factor can exceed 1.
• (C) Inserting at the head of a chain is O(1).
• (D) The worst-case search time is Θ(n).

10 · Rule Card

• h(k) = k mod m (m prime); multiplication method ⌊m·frac(kA)⌋.
• α = n/m. Chaining: insert O(1); unsuccessful search expected α keys (Θ(1 + α)); successful ≈ 1 + α/2.
• Worst case Θ(n). α > 1 allowed.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

hash tablehash functiondivision methodmultiplication methodcollisionload factor αseparate chainingsimple uniform hashingexpected search cost with chaining

12 · Answer Vault