Hashing is where a lot of aspirants lose easy marks, not because the idea is hard but because the questions demand a careful trace. You have to hash keys correctly, resolve collisions in the right order with linear probing, and reason about load factor and expected probes without hand-waving. Below are 12 solved MCQs from KnowledgeGate's published question bank, all previous-year GATE problems with the year marked. Attempt each before the explanation, which is short by design. A note on the deep links: each of these questions is carried as a solved GATE PYQ inside the course, so every one links its exact page. If a concept feels shaky, the full theory sits in the Hashing learn module.
Hash functions and the collision problem
Q1. For the input 4322, 1334, 1471, 9679, 1989, 6171, 6173, 4199 and the hash function x mod 10, which statements are true? 1: 9679, 1989, 4199 hash to the same value. 2: 1471, 6171 hash to the same value. (GATE 2004)
(a) 1 only
(b) 2 only
(c) 1 and 2 only
(d) all elements hash to the same value
Answer: (c) 1 and 2 only. With x mod 10 the hash is just the last digit. 9679, 1989 and 4199 all end in 9, so statement 1 holds. 1471 and 6171 both end in 1, so statement 2 holds. The keys clearly spread across several buckets, so the "all same" option is wrong (see the solved page).
Q2. Which hash function distributes keys most uniformly over 10 buckets (0 to 9) for i ranging from 0 to 2020? (GATE 2015)
(a) h(i) = i^2 mod 10
(b) h(i) = i^3 mod 10
(c) h(i) = (11 x i^2) mod 10
(d) h(i) = (12 x i) mod 10
Answer: (b) h(i) = i^3 mod 10. Every such function depends only on i mod 10, so uniformity depends on whether the last-digit mapping is a bijection. Cubing modulo 10 permutes the residues 0 through 9 (for example 2 to 8, 3 to 7, 7 to 3), so each bucket receives an equal share. Squaring collapses several residues onto the same bucket, so it clusters (see the solved page).
Q3. An adversary stores keys in a hash table and tries to maximise collisions. With k keys, m slots and k greater than m, which hashing strategy is best? (GATE 2023)
(a) division method, h(k) = k mod m
(b) multiplication method with a fixed constant
(c) universal hashing
(d) division if k is prime, else multiplication
Answer: (c) universal hashing. Any fixed hash function is predictable, so an adversary can pick keys that all collide. Universal hashing picks the function at random from a family at run time, giving the guarantee that for any two distinct keys the collision probability is at most 1/m, regardless of how the adversary chooses keys. Randomness is the defence (see the solved page).
Q4. Given n keys and m slots with two simple uniform hash functions h1 and h2, where the scheme uses h1 for odd keys and h2 for even keys, what is the expected number of keys in a slot? (GATE 2022)
(a) m/n
(b) n/m
(c) 2n/m
(d) n/(2m)
Answer: (b) n/m. Every key, whether hashed by h1 or h2, still lands uniformly in one of the m slots, so splitting keys across two uniform functions changes nothing. By linearity of expectation, each key contributes 1/m to a given slot, and summing over n keys gives n/m. That ratio n/m is the load factor, the single most important number in hashing performance (see the solved page).
Open addressing and linear probing
Q5. A hash table has 10 buckets, uses key mod 10 and linear probing. After inserting 43, 165, 62, 123, 142 in order, where does 142 land? (GATE 2005)
(a) 2
(b) 3
(c) 4
(d) 6
Answer: (d) 6. Place 43 at 3, 165 at 5, 62 at 2, then 123 hashes to 3 (occupied) and probes to 4. Now 142 hashes to 2 (occupied by 62), probes to 3 (43), 4 (123), 5 (165), and finally lands at 6. Linear probing means you must carry the earlier collisions forward, or the trace breaks (see the solved page).
Q6. A table of size 11 uses open addressing with linear probing and h(k) = k mod 11. Inserting 43, 36, 92, 87, 11, 4, 71, 13, 14, at which index does the last key 14 land? (GATE 2008)
(a) 3
(b) 4
(c) 6
(d) 7
Answer: (d) 7. Working through the sequence, indices 10, 3, 4, 0, 1 and others fill up as collisions cascade. By the time 14 (which hashes to 3) is inserted, its home and the following slots are taken, so probing carries it forward to index 7. The discipline is to update the table after every insertion before doing the next (see the solved page).
Q7. A table of size 7 (indices 0 to 6) uses h(x) = (3x + 4) mod 7 with linear probing. After inserting 1, 3, 8, 10, what are the contents? (GATE 2007)
(a) 8, _, _, _, _, _, 10
(b) 1, 8, 10, _, _, _, 3
(c) 1, _, _, _, _, _, 3
(d) 1, 10, 8, _, _, _, 3
Answer: (b) 1, 8, 10, _, _, _, 3. Compute each hash: 1 goes to (3+4) mod 7 = 0, and 3 goes to (9+4) mod 7 = 6. Then 8 hashes to (24+4) mod 7 = 0, which is taken, so it probes to index 1. Finally 10 hashes to (30+4) mod 7 = 6, taken, probes to 0 (taken), 1 (taken), and settles at 2. That gives 1, 8, 10 at 0, 1, 2 and 3 at index 6 (see the solved page).
Q8. A table of length 10 uses open addressing with h(k) = k mod 10 and linear probing. The final table holds 42 at index 2, 23 at index 3, 34 at index 4, 52 at index 5, 46 at index 6 and 33 at index 7. Which insertion order produced it? (GATE 2010)
(a) 46, 42, 34, 52, 23, 33
(b) 34, 42, 23, 52, 33, 46
(c) 46, 34, 42, 23, 52, 33
(d) 42, 46, 33, 23, 34, 52
Answer: (c) 46, 34, 42, 23, 52, 33. Reason from the constraints. 42 must precede 52 since both hash to 2 and 52 was probed to 5, and 23 must precede 33 since both hash to 3. Only option (c) keeps every "home before displaced" ordering consistent with the final positions. Reverse-engineering a probing history is just these precedence constraints (see the solved page).
Separate chaining and load factor
Q9. An advantage of a chained hash table (external hashing) over open addressing is (GATE 1996)
(a) worst-case search complexity is lower
(b) space used is less
(c) deletion is easier
(d) none of the above
Answer: (c) deletion is easier. In separate chaining, deleting a key just unlinks a node from its list. Open addressing cannot simply blank a slot, because that would break the probe sequences of other keys, so it needs tombstone markers. That bookkeeping is exactly what chaining avoids (see the solved page).
Q10. A hash table with 100 slots resolves collisions by chaining. Under simple uniform hashing, what is the probability that the first 3 slots stay empty after the first 3 insertions? (GATE 2014)
(a) (97 x 97 x 97) / 100^3
(b) (99 x 98 x 97) / 100^3
(c) (97 x 96 x 95) / 100^3
(d) (97 x 96 x 95) / (3! x 100^3)
Answer: (a) (97 x 97 x 97) / 100^3. With chaining, insertions are independent because collisions are allowed. Each insertion avoids the first three slots with probability 97/100, and the three insertions are independent, so multiply: (97/100)^3. The chaining detail is what makes the events independent rather than "without replacement" (see the solved page).
Q11. In open-address uniform hashing with load factor alpha = n/m less than 1, an unsuccessful search takes at most 1/(1 - alpha) probes. An insertion needs at most how many probes on average? (GATE 2024)
(a) ln(1/(1 - alpha))
(b) 1/(1 - alpha)
(c) 1 + alpha/2
(d) 1/(1 + alpha)
Answer: (b) 1/(1 - alpha). An insertion probes until it finds an empty slot, which is exactly the work of an unsuccessful search: keep probing while slots are occupied (probability alpha) and stop at the first empty one (probability 1 - alpha). That geometric process has expected value 1/(1 - alpha), so insertion matches the unsuccessful-search bound (see the solved page).
Q12. Match each behaviour with its data structure: (p) First In First Out, (q) Lookup operation, (r) Last In First Out with (i) Stacks, (ii) Queues, (iii) Hash Tables. (GATE 2024)
(a) (p)-(ii), (q)-(iii), (r)-(i)
(b) (p)-(ii), (q)-(i), (r)-(iii)
(c) (p)-(i), (q)-(ii), (r)-(iii)
(d) (p)-(i), (q)-(iii), (r)-(ii)
Answer: (a) (p)-(ii), (q)-(iii), (r)-(i). FIFO is the queue, LIFO is the stack, and fast key lookup, typically O(1) on average, is the hash table. This is the one-line summary of why hashing exists: when the operation you care about is lookup by key, no ordered structure beats a good hash table (see the solved page).
How hashing is examined
The set mirrors the paper: hash-function design and collision counting (Q1 to Q4), linear-probing traces both forward and in reverse (Q5 to Q8), and separate chaining with load-factor and expected-probe analysis (Q9 to Q12). Almost every mistake here comes from not updating the table after each insertion, or from confusing the probe counts of chaining and open addressing.
Rebuild the theory and drill the full previous-year sets in the Hashing learn module. GATE aspirants get the complete Data Structures sequence inside GATE Guidance by Sanchit Sir, and the GATE CS Exam category places the topic in the wider syllabus. Solve, review the ones you missed, and come back a week later; the second pass is where the marks lock in.
