Hashing

ACompressed recap

🧾

h(k) = k mod m (prime m) or multiplication method; α = n/m. Chaining: O(1) insert, unsuccessful ≈ α keys (Θ(1 + α)), successful ≈ 1 + α/2, α may exceed 1, worst Θ(n). Open addressing: linear (h + i), quadratic (h + c₁i + c₂i²), double (h₁ + i·h₂); count the home slot; search stops at an empty slot; tombstones for deletion; linear → primary clustering. Expected probes: 1/(1 − α) unsuccessful, (1/α)ln(1/(1 − α)) successful. Collision probabilities: product m(m−1)…/mⁿ, (1 − k/m)ⁿ, C(n,2)/m pairs.

BMerged rule card

2.2.1 Hash tables, hash functions, load factor; separate chaining

• h(k) = k mod m (m prime); multiplication method ⌊m·frac(kA)⌋.
• α = n/m. Chaining: insert O(1); unsuccessful search expected α keys (Θ(1 + α)); successful ≈ 1 + α/2.
• Worst case Θ(n). α > 1 allowed.

2.2.2 Open addressing: linear probing, quadratic probing, double hashing

• Linear: (h + i) mod m; quadratic: (h + c₁i + c₂i²) mod m; double: (h₁ + i·h₂) mod m.
• Insert at the first empty slot; search until key or empty slot; deletion uses tombstones.
• Linear → primary clustering; quadratic → secondary; double hashing avoids both (h₂ coprime to m).
• Probe count includes the home slot.

2.2.3 Expected probes and collision probabilities

• Open addressing (uniform): unsuccessful ≤ 1/(1−α); successful ≤ (1/α)ln(1/(1−α)).
• Chaining: unsuccessful Θ(1 + α); successful ≈ 1 + α/2.
• P(no collision) = m(m−1)…(m−n+1)/mⁿ; P(k given slots empty) = (1 − k/m)ⁿ.
• E[empty slots] = m(1 − 1/m)ⁿ; E[colliding pairs] = C(n,2)/m.

CInterleaved GATE-style questions

Q1NAT1 markChaining

m = 5, h(k) = k mod 5, chaining. Keys 7, 12, 17, 3, 22, 8. How many keys are in slot 2's chain?

Numerical answer: ________

Q2NAT2 marksLinear probing

m = 7, h(k) = k mod 7, linear probing. Insert 50, 700, 76, 85, 92, 73, 101. Which slot holds 101?

Numerical answer: ________

Q3NAT2 marksProbes

m = 11, h(k) = k mod 11, linear probing; keys 10, 22, 31, 4, 15, 28, 17, 88, 59. How many probes did inserting 88 take?

Numerical answer: ________

Q4NAT2 marksDouble hashing

m = 13, h₁(k) = k mod 13, h₂(k) = 7 − (k mod 7). After inserting 25, 37, 18, 55, 22, which slot does 35 take?

Numerical answer: ________

Q5NAT1 markUnsuccessful probes

Open addressing, uniform hashing, α = 0.95. Expected probes for an unsuccessful search?

Numerical answer: ________

Q6NAT2 marksEmpty slots

Simple uniform hashing: 4 keys into 8 slots. Probability that slot 0 is still empty?

Numerical answer: ________

Q7MCQ1 markDeletion

In open addressing, a deleted key's slot is marked "deleted" rather than emptied because:

• (A) it makes insertions faster
• (B) the hash function requires it
• (C) searches for other keys may need to probe past it
• (D) it saves memory

Q8MSQ2 marksFacts

Which are true?

• (A) Double hashing always needs m to be a power of 2.
• (B) Linear probing suffers from primary clustering.
• (C) With open addressing, α must be at most 1.
• (D) With chaining, α can be greater than 1.

DAnswer Vault