Medium ●●

#️⃣ Hashing

Why it matters: Insert keys into a small table by hand: a favourite 1 or 2 mark question every few years.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 3 done.

Formulas

Load factor
α = n / m
Chaining
unsuccessful: Θ(1 + α); successful: ≈ 1 + α/2; worst case O(n)
Open addressing (uniform hashing)
unsuccessful ≤ 1/(1 − α); successful ≤ (1/α) ln(1/(1 − α))
Probe sequences
linear: h + i; quadratic: h + c₁i + c₂i²; double: h₁ + i·h₂ (all mod m)
Collisions
expected number of colliding pairs among n keys in m slots ≈ n(n − 1)/(2m)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Insert keys with linear probing / chaining and read the table
Do the arithmetic carefully, slot by slot, and check which slots are empty at the end.
★★★
Number of collisions or longest chain
Count keys per slot, or compare strategies on the same keys.
★★★
Probe count for a successful / unsuccessful search
Chains: average length; open addressing: 1/(1 − α).
★★★
Which statement about hashing is true
Clustering, deletion, load factor above 1 for chaining, why m prime.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

6 real questions from the official GATE CSE papers (2014 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

6 questions · 0 correct of 0 attempted · marks 0 / 9

Year:
GATE 2025 CS1 · Q65NAT2 marks
In a double hashing scheme, h1(k) = k mod 11 and h2(k) = 1 + (k mod 7) are the auxiliary hash functions. The size m of the hash table is 11. The hash function for the i-th probe in the open address table is [h1(k) + i·h2(k)] mod m. The following keys are inserted in the given order: 63, 50, 25, 79, 67, 24. The slot at which key 24 gets stored is ______.
GATE 2023 · Q20MCQ1 mark
An algorithm has to store several keys generated by an adversary in a hash table. The adversary is malicious who tries to maximize the number of collisions. Let k be the number of keys, m be the number of slots in the hash table, and k > m. Which one of the following is the best hashing strategy to counteract the adversary?
GATE 2022 · Q16MCQ1 mark
Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h1 and h2. Further suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?
GATE 2021 Set 1 · Q47MSQ2 marks
Consider a dynamic hashing approach for 4-bit integer keys:
1. There is a main hash table of size 4.
2. The 2 least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand.
5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision. The state of the hash table: entry 00 is empty; entry 01 is a tree whose left child (3rd bit 0) is a single key and whose right child (3rd bit 1) is split on the 4th bit into two keys; entry 10 is a tree with one key on each side of the 3rd bit; entry 11 holds a single key. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?

One or more options may be correct. Select all that apply, then submit.

GATE 2020 · Q23NAT1 mark
Consider a double hashing scheme in which the primary hash function is h1(k) = k mod 23, and the secondary hash function is h2(k) = 1 + (k mod 19). Assume that the table size is 23. Then the address returned by probe 1 in the probe sequence (assume that the probe sequence begins at probe 0) for key value k = 90 is ______.
GATE 2014 Set 1 · Q40MCQ2 marks
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

Common traps

Chaining can have α > 1; open addressing cannot.
In open addressing a deleted slot must be marked, not emptied.
Quadratic probing may never reach some slots even when the table is not full.
Check whether the question inserts at the head or tail of a chain.