Hashing: separate chaining and load factor
Contract and prerequisite
Use array, linked-list and asymptotic-bounds foundations. A hash table implements a dictionary of distinct keys; updating an existing key replaces its value. A hash function maps keys into m buckets, indexed 0,...,m−1. Computing the hash and comparing keys are assumed O(1); variable-length strings require accounting for their lengths separately.
1. Collisions do not imply equal keys
Separate chaining stores a list of records in each bucket. Search computes h(k) and compares k with keys in that list until found or the list ends. Insert a new record at the front after checking whether it already exists if dictionary semantics require uniqueness. Delete finds and unlinks the matching record. A pointer to a node can remove the search cost only with a suitable representation, such as a doubly linked list; a singly linked list may need the predecessor.
Example: m=5, h(k)=k mod 5. Insert 7,12,4,17 at the head. Bucket 2 evolves [7], [12,7], [17,12,7]; bucket 4 is [4]. Search 7 makes three key comparisons. Unsuccessful search 22 also scans three records, because 22 hashes to bucket 2 but differs from every key. A collision means equal hash location, not equal original key.
2. Load factor and expected time
Load factor α=n/m is average records per bucket. It may exceed 1 in chaining. Under simple uniform hashing, each key is equally likely to hash to each bucket, with the independence assumptions needed for the expected chain-length analysis. An unsuccessful search has expected chain length α and expected time Θ(1+α), including hash computation. A successful search also takes expected Θ(1+α) under the standard uniform/random-order model. Exact constants depend on insertion order and which keys are queried; do not memorize an exact comparison count without those assumptions.
For n=24,m=8, α=3. This does not mean every bucket has exactly three records. Even with average three, one bucket could hold all 24 for an unlucky or adversarial choice. Worst-case search is Θ(n), not O(1). Hashing's expected guarantee is not a binary-search-style worst-case guarantee.
3. Insertion and resizing qualifications
If a key is guaranteed absent and head insertion is allowed, the pointer splice is O(1), excluding allocation and any hash cost beyond the model. If uniqueness must be checked, insertion includes a search and is expected Θ(1+α). These are different operation contracts.
Maintain α=O(1) by growing m proportionally to n and rehashing every key with the new bucket count. Rehashing costs Θ(n+m_new) for initializing the new bucket array and moving records, which is Θ(n) for proportional capacity. With geometric growth, occasional linear rehashes can yield amortized constant insertion overhead; a single insertion that triggers resizing is still linear. “Expected” averages over hashing randomness, while “amortized” averages a sequence's total cost; neither means every operation is constant.
4. Space and pitfalls
Total storage is Θ(m+n), including empty bucket heads and records. Chaining can store more keys than buckets; α<1 is not required. A good hash function must distribute the relevant keys, not merely return a valid bucket. The deterministic mod example is for traces, not proof of uniform hashing. When comparing dictionary designs, state collision handling, key-comparison cost, load factor, expected versus worst-case cost, and whether duplicate checking is required.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. 24 keys in 8 chained buckets give α:
A. 1/3 B. 3 C. 8 D. 24
Answer: B
A: The ratio is n/m, not m/n.
B: 24/8=3.
C: This is bucket count.
D: This is key count.
P02. Under uniform hashing, expected unsuccessful search time is:
A. Θ(α) even when α→0 B. Θ(1+α) C. Always Θ(n) D. Always Θ(log n)
Answer: B
A: Hash and bucket access cost remain.
B: Hash work plus expected chain scan.
C: Worst case is not expectation.
D: There is no binary-search ordering.
P03. Head-insert 7,12,4,17 with h(k)=k mod 5. Search 7 comparisons?
A. 1 B. 2 C. 3 D. 4
Answer: C
A: 17 is first.
B: 12 is second.
C: Bucket 2 is [17,12,7].
D: 4 is in another bucket.
P04. Which statement is correct for chaining?
A. α must be below 1 B. Colliding keys are identical C. All buckets have exactly α records D. α can exceed 1
Answer: D
A: Chains permit multiple records.
B: Only their hash values coincide.
C: α is an average.
D: More keys than buckets are allowed.
P05. Worst-case search if all n keys collide?
A. Θ(1) B. Θ(log n) C. Θ(n) D. Θ(n²)
Answer: C
A: A long list may need full scanning.
B: The list is not searched by binary search.
C: Up to n key comparisons are needed.
D: One scan is linear, not quadratic.
P06. One insertion triggering proportional rehash may take:
A. Θ(1) necessarily B. Θ(n) C. Θ(log n) necessarily D. Zero work
Answer: B
A: Amortization does not bound every individual operation.
B: All existing keys must be moved.
C: Moving all records is not logarithmic.
D: New storage and rehashing require work.
Sources and scope
Aligned to the 2026 course. This lesson covers the stated slice, not the entire Algorithms syllabus. All numerical examples and questions are original. No claim of 2027 completeness.
Sign in to keep your progress. Sign in