Hash Tables & Linear Probing

The last lesson ended on a wish: a structure that does not search for a value but computes where it lives, jumping straight there in O(1). That structure exists, and the trick is almost suspiciously simple. A dictionary lookup does not search and does not loop — it computes the address. A hash table runs a hash function on the key to get a slot number, then goes straight there. Store and retrieve both cost one computation plus one slot read, so lookup is O(1) on average, whether the table holds ten keys or ten million. It is the engine under Python’s dict, every GROUP BY and hash join in a database, and the deduplication step in most data pipelines — which is why GATE keeps testing it.

The catch: two different keys can land on the same slot — a collision. How you resolve collisions is the whole subject, and it is exactly what GATE drills.

Hashing into slots

Pick a table of m slots and a hash function h(key) that returns an index in 0 … m−1. A typical exam hash is arithmetic, e.g. h(x) = 3x mod 10 for a size-10 table. Insert a key by computing its slot; look it up by recomputing the same slot. Deterministic and direct — the key tells you exactly where to go.

When h sends two keys to the same slot, you need a collision strategy. There are two classic families.

Chaining vs open addressing

• Chaining — each slot holds a list (linked list or small array) of all keys that hash there. Insert appends to the list; lookup hashes to the slot, then scans its list. Average lookup cost is O(1 + alpha) where alpha is the load factor below.
• Open addressing — every key lives in the array itself. On a collision you probe for another slot. Linear probing tries the next slots in order: h, h+1, h+2, … (mod m) until an empty one appears. Lookup follows the same path until it finds the key or hits an empty slot.

The load factor is alpha = n / m (items over slots). Chaining tolerates alpha > 1; open addressing cannot exceed alpha = 1 (the array fills up) and slows sharply well before that.

How GATE asks this

The signature question is a NAT: a small table, an arithmetic hash, linear probing, and a fixed insertion order — “which slot does key k end up in?” You trace the probe sequence by hand. GATE DA has asked this in both 2024 and 2025. A second NAT flavour gives a load factor and asks for the expected number of probes, using the open-addressing estimate 1/(1 − alpha) (asked 2024).

Worked example — a real GATE DA 2025 question

Table size m = 10, hash h(x) = 3x mod 10, collisions resolved by linear probing. Insert 1, 4, 5, 6, 14, 15 in this order. Where do 14 and 15 land?

Compute each home slot, and when it is occupied, step forward +1 (mod 10) until empty:

h(1)  = 3·1  mod 10 = 3   → slot 3 empty   ⇒ slot 3
h(4)  = 3·4  mod 10 = 2   → slot 2 empty   ⇒ slot 2
h(5)  = 3·5  mod 10 = 5   → slot 5 empty   ⇒ slot 5
h(6)  = 3·6  mod 10 = 8   → slot 8 empty   ⇒ slot 8

h(14) = 3·14 mod 10 = 2   → slot 2 holds 4   (collision)
                          → probe 3 holds 1   (collision)
                          → probe 4 empty     ⇒ slot 4
h(15) = 3·15 mod 10 = 5   → slot 5 holds 5    (collision)
                          → probe 6 empty     ⇒ slot 6

So 14 lands in slot 4 and 15 lands in slot 6 — the answer to the 2025 question. The final table:

For the expected-probe variant (2024): an insertion behaves like an unsuccessful search — it probes until it hits an empty slot — so its expected probe count is about 1/(1 − alpha). At alpha = 0.5 that is 1/(1 − 0.5) = 2 probes; at alpha = 0.9 it explodes to 10.

A question to carry forward

Hash tables buy that O(1) lookup with a quiet sacrifice: they throw away all sense of order. The hash function deliberately scatters keys, so the slots hold them in no meaningful sequence at all. Ask a hash table for its smallest key, or to list keys in sorted order, or for everything between 40 and 60, and it simply has no idea — it would have to scan every slot. Yet plenty of problems need fast lookup and a sense of order at once. Here is the thread onward: what shape organises data so that it branches hierarchically — keeping a structure you can search and walk in order — and how do you visit every element of it systematically?

In one breath

• A hash table computes a slot with h(key) and goes straight there — O(1) average lookup, no searching. Engine behind dict, GROUP BY, dedup.
• A collision (two keys, one slot) is resolved by chaining (a list per slot, tolerates alpha > 1) or open addressing (keys live in the array; alpha ≤ 1).
• Linear probing: on a collision try h, h+1, h+2, … (mod m) until empty. GATE traces this by hand (h(x)=3x mod 10, insert order → which slot? — 2024 & 2025).
• Load factor alpha = n/m; expected probes for an insertion / unsuccessful search ≈ 1/(1 − alpha) (2 at alpha=0.5, 10 at 0.9).
• Primary clustering lengthens runs; use the unsuccessful-search probe figure for insertions, not the successful one.

Practice