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. GATE keeps returning to the same three skills: spreading keys, tracing probes without losing the table, and turning a load factor into a probe count. Work every trace on paper before you read the answer. 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. 3: All elements hash to the same value. 4: Each element hashes to a different value. (GATE 2004)
(a) 1 only
(b) 2 only
(c) 1 and 2 only
(d) 3 or 4
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 eight keys land on last digits 2, 4, 1, 9, 9, 1, 3 and 9, so five buckets are in use: statements 3 and 4 both fail and (d) is out (open it in the hash-functions PYQ drill).
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 option depends only on i mod 10, so uniformity comes down to whether the last-digit mapping is one-to-one. Cubing modulo 10 permutes the residues 0 through 9 (2 to 8, 3 to 7, 7 to 3), so the 2021 inputs split as evenly as ten buckets allow: 203 in bucket 0 and 202 in each of the others. Squaring collapses the ten residues onto six buckets (0, 1, 4, 5, 6, 9); multiplying by 11 changes nothing, since 11 is 1 modulo 10; and 12i mod 10 only ever lands on even buckets (open it in the hash-functions PYQ drill).
Q3. An algorithm has to store keys generated by a malicious adversary who is trying to maximise collisions. With k keys, m slots and k greater than m, which hashing strategy best counteracts the adversary? (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. Randomness is the defence (open it in the hash-functions PYQ drill).
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 (open it in the hash-functions PYQ drill).
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 (open it in the open-addressing PYQ drill).
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. Track the table as you go: 43 lands at 10, 36 at 3 and 92 at 4, then 87 hashes to 10 (taken) and probes to 0, and 11 hashes to 0 (taken) and probes to 1. Next 4 hashes to 4 (taken) and probes to 5, 71 hashes to 5 (taken) and probes to 6, and 13 sits at 2. So 14 hashes to 3 and finds 3, 4, 5 and 6 all occupied, landing at index 7 (open it in the open-addressing PYQ drill).
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 (open it in the open-addressing PYQ drill).
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. Read the probe distances off the final table. 52 hashes to 2 but ended at 5, so slots 2, 3 and 4 were already full when it arrived: 42, 23 and 34 all precede it. 33 hashes to 3 but ended at 7, so 3, 4, 5 and 6 were full: 23, 34, 52 and 46 all precede it. That kills (a), where 23 comes after 52, (b), where 46 comes after 33, and (d), where 33 comes before 23, leaving (c). Each displaced key dates every slot it walked over (open it in the open-addressing PYQ drill).
Separate chaining, load factor and where hashing wins
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 (open it in the chaining and analysis PYQ drill).
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, so the three probabilities multiply to (97/100)^3 (open it in the chaining and analysis PYQ drill).
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 (open it in the chaining and analysis PYQ drill).
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 (open it in the chaining and analysis PYQ drill).
How hashing is examined
The set mirrors the paper: hash-function design and expected-occupancy reasoning (Q1 to Q4), linear-probing traces forward and in reverse (Q5 to Q8), separate chaining with load-factor and expected-probe analysis (Q9 to Q11), and one placement question that puts hashing against the ordered structures (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.
