Hashing Questions in GATE CSE: Probing, Load Factor and Traps

Hashing questions in GATE CSE are almost always the same exercise. A small table is printed, a hash function and a collision rule are stated, a key sequence is given, and you report the final contents, the slot of one key, or a probe count. Nothing here is deep. Marks are lost on wraparound, on the probe-counting convention, and on assuming the answer does not depend on the order the keys arrived in.

Key takeaways

• Every index is taken modulo the table size. The probe sequence wraps from slot $m - 1$ back to slot 0.
• A probe is a slot you examine. The home slot counts as the first probe, so probes equal collisions plus one.
• Which key ends up in which slot depends on the insertion order. Reorder the keys and the table changes.
• Load factor is $n/m$. It can exceed 1 for chaining, never for open addressing.
• A naive delete in open addressing breaks later searches. The fix is a tombstone, not an empty cell.

Where hashing sits in the paper

Hashing is named verbatim in the Algorithms line of the official CS syllabus for 2027: searching, sorting, hashing. It is not a borderline topic, even though the table, the chains and the probe arithmetic are pure data structures work.

Third-party analyst compilations put Programming and Data Structures at 6 to 13 marks per paper from 2009 to 2026, averaging near 9.9 with a stable direction. Taken with Algorithms the block averages about 18 marks, the largest after mathematics and General Aptitude. The split moves every year, which is why the two are prepared as one unit: 2021 was 6 plus 11, while 2026 shift 1 was 9 plus 10. One analyst's count for 2026 shift 2 put Programming and Data Structures at 8 questions, the highest of any subject that shift. These figures are unofficial, the 2014 and 2015 values merge data structures with algorithms in the source, and analysts disagree by 2 to 3 marks on borderline questions. Check the current notification for the pattern that applies to your year.

Several concepts from the 2000 to 2005 papers have reappeared in near-identical form after 2015, and the probe sequence of a hash table is named as one of them. The full subject ranking sits in the Algorithms important topics guide, and the broader tracing patterns are in the guide to data structure question patterns.

The standard exercise, traced end to end

Take a table of size 7, slots 0 to 6, with $h(k) = k \bmod 7$ and linear probing. Insert 25, 12, 13, 6, 19 in that order.

Final table: slot 0 holds 6, slot 1 holds 19, slots 2 and 3 are empty, 4 holds 25, 5 holds 12, 6 holds 13. Total probes across the five insertions: 9. Total collisions: 4.

Two things in that trace carry marks. Key 6 wrapped from slot 6 to slot 0 because $7 \bmod 7 = 0$, and candidates who write the sequence as 6, 7 without the modulo lose the question there. And key 19 cost four probes although only one other key hashed to its home slot, because 25, 12 and 13 had already merged into one run. That is primary clustering: separate home slots grow into a single block, and any key landing anywhere in the block walks its whole length.

Why insertion order matters

Reverse the order and insert 19, 13, 12, 6, 25 into an empty table of the same size. Now 19 takes slot 5 on its first probe, 13 takes slot 6, 12 collides at 5 and 6 and lands in slot 0, and you finish with a different table from the same key set.

With linear probing the set of occupied slots comes out the same whichever order you use, which is a useful check on your work. What changes is which key sits in which slot, and therefore the probe count for any individual key. A question asking for the slot of the last key, or the probes needed by one named key, is order-sensitive by construction. One asking only which slots are full is not. For quadratic probing and double hashing even the occupied set can change with the order.

Three probe sequences on one table

Return to the state after 25, 12, 13 and 6 are in place, and insert 19 by each rule. Its home slot 5 is occupied.

Here $h_2(k) = 1 + (k \bmod 5)$, so:

Same key, same table, three different answers. Read the stated rule before computing anything, because setters switch the quadratic form between $i^2$, $c_1 i + c_2 i^2$, and variants that alternate sign.

Three properties are worth memorising.

• Linear probing suffers primary clustering, but it never fails to find a free slot while one exists.
• Quadratic probing breaks up long runs and suffers only secondary clustering: keys sharing a home slot still share their whole probe sequence. With a prime table size, a table at most half full is guaranteed to admit the new key. Above half full it can fail even when slots remain, because $\big(h(k) + i^2\big) \bmod m$ for a prime $m$ reaches only about $(m + 1)/2$ distinct slots. The trace above was four sevenths full, so we were lucky.
• Double hashing needs $h_2(k)$ never to be zero, or every probe returns the home slot and the loop never terminates. It should also be coprime with $m$ so the sequence visits every slot. A prime $m$ with $h_2(k) = 1 + \big(k \bmod (m - 1)\big)$ satisfies both. A table size of 8 with an even $h_2$ does not, and the sequence then cycles through half the table.

Separate chaining and the load factor

In separate chaining each slot holds a linked list and colliding keys are appended, so no key is ever displaced. The load factor $\alpha = n/m$ is the average chain length and is allowed to exceed 1: 150 keys in 100 slots gives $\alpha = 150/100 = 1.5$, an average chain of one and a half nodes. Under open addressing $\alpha$ can never exceed 1, because each key occupies its own slot. The trade is a pointer per node against a table that degrades sharply as it fills.

Expected probes, used rather than derived

Under the simple uniform hashing assumption the closed forms below are all you need. You are never asked to derive them.

At $\alpha = 0.5$ under uniform hashing an unsuccessful search costs $\displaystyle \frac{1}{1 - 0.5} = 2$ probes and a successful one $\displaystyle \frac{1}{0.5} \ln 2 \approx 1.39$. At $\alpha = 0.9$ the figures are 10 and about 2.56. The asymmetry is the whole point: an unsuccessful search must walk to an empty slot, while a successful one stops at a key inserted when the table was less full. Under linear probing that same $\alpha = 0.9$ gives $\displaystyle \frac{1}{2}\left(1 + \frac{1}{0.1^2}\right) = 50.5$ probes for an unsuccessful search, which is why the $1/(1 - \alpha)^2$ term matters. These belong on your formula sheet.

Deletion and tombstones

This is the part most candidates have never traced. In the final table above, delete 13 from slot 6 by blanking the cell, then search for 19. Its home slot 5 holds 12, so you move to slot 6, find it empty, and conclude 19 is absent, although 19 is sitting in slot 1. The delete silently broke the probe path.

The fix is a tombstone: mark the cell deleted rather than empty. A search treats a tombstone as occupied and keeps probing; an insertion treats it as free and may reuse it. Tombstones then accumulate, unsuccessful searches get slower even as the real key count falls, and the table needs periodic rehashing. In chaining none of this arises, because deleting a node from a list disturbs nothing else.

The traps in one list

• Counting the home slot as probe zero when the question counts from one, or the reverse. Collisions equal probes minus one per insertion.
• Mixing up the successful and unsuccessful formulas. Unsuccessful is always larger.
• Forgetting the modulo, so the sequence runs off the end of the table instead of wrapping to slot 0.
• Treating a chained table as constant time in the worst case. If every key collides the chain has $n$ nodes and a search is $\Theta(n)$.
• Assuming quadratic probing always finds a free slot. The guarantee needs a prime size and a table at most half full.
• Letting $h_2(k)$ return zero, or choosing an $h_2$ sharing a factor with the table size.

The cross-subject version of this list is in common mistakes that cost marks in GATE CSE.

How to practise

Keep one table of size 7 or 11 and one key list of six to eight values, and run every scheme on it by hand: linear, quadratic, double hashing, then chaining. Write the probe sequence as an explicit list of slot numbers before deciding anything, and note the probe count for each insertion in a column as you go. Then delete one key from the middle of a run and search for a key behind it, so the tombstone problem becomes something you have seen rather than read about.

Then shuffle the same key list and redo it. Watching the same keys land in different slots fixes the order-dependence permanently. The Algorithms chapter of the GATE CSE 2027 book carries a full bank of these traces written out slot by slot, including the insertion-order counting variant this article only mentions.