Hash Table Chaining MCQs: 12 Solved Questions with Explanations

Chaining looks easy until a question moves beyond the definition and tests load factor, worst-case chains, deletion or bucket-occupancy probability. Choose an option and write one line of reasoning before reading each explanation, and keep your workings beside the question. For Questions 1, 8 and 12, use the Chaining & Perf Analysis practice hub. The Coding & DSA Courses for Placements place hashing in the wider DSA sequence.

Chaining formulas and one worked hash-table trace

Separate chaining is a collision-resolution method in which h(k) chooses one of m buckets, and every key mapped to the same bucket is stored in that bucket's chain. The load factor is alpha = n/m. Under simple uniform hashing, the expected chain length is alpha, so expected search takes O(1 + alpha). The worst case is O(n) when all n keys enter one bucket. The broader hashing and collision resolution explainer compares this method with probing.

Take m = 7, h(k) = k mod 7, and insert 10, 17, 24, 31, 6, 13 in that order. The first four keys all give remainder 3, so bucket 3 is 10 -> 17 -> 24 -> 31. Keys 6 and 13 give remainder 6, so bucket 6 is 6 -> 13; every other bucket is empty. Here n = 6 and alpha = 6/7 = 0.857. With append-order chains, a successful search for 24 checks three nodes. An unsuccessful search for 38 checks all four nodes in bucket 3 because 38 mod 7 = 3. Expected O(1 + alpha) is an average under a hashing assumption, not a guarantee for every key set.

Chaining MCQs 1-3: definition and collision resolution

Question 1

What is chaining in the context of hash tables?

• A. A way to resolve collisions by rehashing

• B. A way to resolve collisions by creating a linked list of entries having the same hash value

• C. A way to increase the capacity of the hash table

• D. None of the above

Correct answer: B.

When two or more keys receive the same hash index, chaining keeps those entries together in a secondary structure at that index, conventionally a linked list. That is exactly the mechanism stated in B. Rehashing computes another position or rebuilds a table, while increasing capacity is resizing. Neither operation defines chaining, so A and C do not fit.

Question 2 (TPSC 2025)

In a hash table, which of the following is used to resolve collisions ?

• A. Hashing

• B. Chaining

• C. Backtracking

• D. Sorting

Correct answer: B.

Hashing computes the index and can send two keys there. Chaining resolves that collision by storing both in the bucket's chain. Backtracking and sorting do not do this, so B is correct.

Practice this question

Question 3 (UGC NET 2023)

Which collision resolution technique involves maintaining a linked list of collided keys ?

• A. Linear probing

• B. Quadratic probing

• C. Chaining

• D. Double hashing

Correct answer: C.

Chaining keeps collided keys at one table index and follows a linked structure. The other three methods use probe sequences to seek alternative array slots. Only C matches the linked-list description.

Practice this question

Chaining MCQs 4-6: compare methods and implementation cost

Question 4 (UGC NET 2025)

Match List I with List II

Choose the correct answer from the options given below:

• A. A-II, B-III, C-I, D-IV

• B. A-II, B-III, C-IV, D-I

• C. A-III, B-I, C-IV, D-II

• D. A-IV, B-II, C-I, D-III

Correct answer: C.

Chaining maps to linked list at index (A-III). Linear probing checks the next slot (B-I). Quadratic probing takes quadratic steps (C-IV). Double hashing uses a second hash function (D-II). That tuple is option C.

Practice this question

Question 5 (Capgemini 2024)

What is the time complexity of insert function in a hash table using a doubly linked list?

• A. O(1)

• B. O(n)

• C. O(log n)

• D. O(n log n)

Correct answer: A.

After hashing to the bucket, insert the node at the chain's head. Updating the head and a fixed number of pointers takes O(1), so A is correct. A duplicate check or tail search would add traversal cost.

Practice this question

Question 6 (LTI Mindtree 2025)

Which of the following is a disadvantage of using separate chaining using linked lists?

• A. It requires many pointers

• B. It requires linked lists

• C. It uses array

• D. It does not resolve collision

Correct answer: A.

Each linked node carries pointer fields besides its key or value, so A identifies the overhead. B names the implementation, C is normal table storage, and D is false because chaining resolves collisions.

Practice this question

Chaining MCQs 7-9: deletion and worst-case performance

Question 7 (GATE 1996)

An advantage of chained hash table (external hashing) over the open addressing scheme is

• A. Worst case complexity of search operations is less

• B. Space used is less

• C. Deletion is easier

• D. None of the above

Correct answer: C.

Chaining deletes a found node by unlinking it. Open addressing needs a tombstone or equivalent treatment so later searches are not stopped early. Worst-case search remains linear, and linked nodes use extra pointer space. A and B fail, leaving C.

Practice this question

Question 8

What is the worst-case time complexity of searching in a hash table using chaining?

• A. O(1)

• B. O(n)

• C. O(n^2)

• D. O(log n)

Correct answer: B.

If all n keys hash to bucket 3, an unsuccessful search there inspects all n nodes before reporting absence. That takes O(n). Uniform hashing and a controlled load factor improve expected search, but not this worst case.

Question 9 (CoCubes 2023)

What is the worst-case time complexity of operations in a hash table?

• A. O(1)

• B. O(log n)

• C. O(n)

• D. O(n^2)

Correct answer: C.

Collisions can put all n entries in one chain. Search and deletion may traverse it, while insertion may do so when checking for an existing key. Thus worst-case time is O(n), not expected-case O(1). Next, try the broader hash-function MCQs.

Practice this question

Chaining MCQs 10-12: chain lengths and bucket probability

Question 10 (GATE 2014)

Consider a hash table with 9 slots. The hash function is $h(k) = k \ mod \ 9$. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

• A. 3, 0, and 1

• B. 3, 3, and 3

• C. 4, 0, and 1

• D. 3, 0, and 2

Correct answer: A.

Compute the residues: 5->5, 28->1, 19->1, 15->6, 20->2, 33->6, 12->3, 17->8, 10->1. Bucket 1 has three keys; buckets 0, 4 and 7 are empty. The maximum is 3, the minimum is 0, and the average over all slots is 9/9 = 1. The tuple 3, 0, 1 makes A correct.

Practice this question

Question 11 (GATE 2014)

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

• A. $(97 × 97 × 97)/100^3$

• B. $(99 × 98 × 97)/100^3$

• C. $(97 × 96 × 95)/100^3$

• D. $(97 × 96 × 95)/(3! × 100^3)$

Correct answer: A.

One insertion avoids the first three slots with probability 97/100. Chaining permits repeated choices of a safe slot, so 97 does not decrease. Independence gives (97/100)^3 = (97 x 97 x 97)/100^3, which is A.

Practice this question

Question 12

Given a hash table with n keys and m slots under simple uniform hashing, collisions are resolved by chaining. What is the probability that the first slot ends up empty?

• A. $(1/m)^n$

• B. $(1-1/m)^n$

• C. $1/n$

• D. $(1-1/n)^m$

Correct answer: B.

One key misses the first slot with probability 1 - 1/m. All n independent keys must miss it, so the probability is (1 - 1/m)^n and B is correct. With m = 10 and n = 4, the check is 0.9^4 = 0.6561.

What the score says about the weak concept

Use the missed question numbers as a diagnosis. If Questions 1-4 were wrong, revise chaining versus probing. If 5-7 were wrong, revisit pointer overhead, head insertion and deletion. If 8-12 were wrong, revise worst-case chains, load factor and independent occupancy events.

Keep four traps visible: O(1) is expected, not guaranteed; chaining does not consume a new empty table slot for every collision; probability questions allow repeated choices of the same safe slot; and average chain length over all buckets is n/m, including empty buckets. Review the weak concept for ten minutes, then redo only that group with no answer visible.

Chaining revision checklist and the next practice step

Chaining stores keys with the same index in one chain.

Expected search depends on alpha = n/m.

A pathological chain makes search O(n).

Bucket-empty probabilities multiply independent miss probabilities.

For the full exam route, continue with GATE Guidance by Sanchit Sir. For placement-focused preparation, continue with Coding for Placements. Attempt all 12 questions again in one sitting, writing the residue or probability calculation beside every numerical. Move to the linked hash-function MCQ collection only after you answer the previously missed group correctly.