∑GATE DA Atlas
GATE DA / Programming, Data Structures and Algorithms

Hash Tables

Hash functions and the division and multiplication methods, the load factor, collision resolution by separate chaining and by open addressing (linear probing, quadratic probing, double hashing), primary and secondary clustering, deletion with tombstones, expected probe counts, rehashing, Python's dict and set, and typical hashing patterns in algorithms.

Section 49 practice questions

The idea

A hash table stores key–value pairs in an array of mm buckets. A hash function hh maps each key to an index h(k)∈{0,…,m−1}h(k) \in \{0, \dots, m - 1\}, giving insert, search and delete in O(1)O(1) expected time.

"cat" "dog" h(k) 0 1 2 3 4 cat: 3 dog: 5 owl: 1 collision → chain
Separate chaining: each bucket holds a list of the entries that hash there.

Hash functions

A good hash function is fast, deterministic, and spreads keys uniformly.

MethodFormulaNotes
Divisionh(k)=k mod mh(k) = k \bmod mchoose mm prime, not near a power of 2
Multiplicationh(k)=⌊m (kA mod 1)⌋h(k) = \lfloor m\,(kA \bmod 1)\rfloor, 0<A<10 < A < 1mm can be a power of 2; A≈0.618A \approx 0.618 works well
Stringspolynomial rolling hash ∑ci pi mod m\sum c_i\,p^i \bmod malso used in Rabin–Karp
Universal hashingpick hh at random from a familyguarantees good expected behaviour for any input

The load factor is α=n/m\alpha = n/m (keys per bucket).

Collision resolution

Collisions are unavoidable once nn is moderate: with mm buckets, a collision becomes likely after about πm/2\sqrt{\pi m/2} insertions (the birthday paradox).

Separate chaining

Each bucket holds a linked list (or dynamic array) of entries.

  • Insert O(1)O(1); search and delete O(1+α)O(1 + \alpha) expected.
  • Works for any α\alpha, degrades gracefully; worst case O(n)O(n) if everything collides.

Open addressing

All entries live in the array; on a collision, follow a probe sequence h(k,0),h(k,1),…h(k, 0), h(k, 1), \dots until an empty slot is found.

Probingh(k,i)h(k, i)Drawback
Linear(h(k)+i) mod m(h(k) + i) \bmod mprimary clustering: long runs of occupied slots grow
Quadratic(h(k)+c1i+c2i2) mod m(h(k) + c_1i + c_2i^2) \bmod msecondary clustering: keys with the same h(k)h(k) share a sequence; may not visit every slot
Double hashing(h1(k)+i h2(k)) mod m(h_1(k) + i\,h_2(k)) \bmod mbest spread; needs h2(k)≠0h_2(k) \ne 0 coprime to mm
  • Requires α≤1\alpha \le 1; performance collapses as α→1\alpha \to 1.
  • Deletion uses a tombstone ("deleted") marker: searches skip over it, insertions may reuse it.
  • Expected probes (uniform hashing): unsuccessful ≤11−α\le \frac{1}{1-\alpha}; successful ≤1αln⁡11−α\le \frac{1}{\alpha}\ln\frac{1}{1-\alpha}. Linear probing: about 12(1+1(1−α)2)\frac12\left(1 + \frac{1}{(1-\alpha)^2}\right) and 12(1+11−α)\frac12\left(1 + \frac{1}{1-\alpha}\right).

Rehashing

When α\alpha crosses a threshold (Python dicts resize at about 2/3 full), allocate a larger table (typically double) and re-insert everything: O(n)O(n) for that operation but amortised O(1)O(1) per insertion.

Python's dict and set

  • Both are open-addressing hash tables; average O(1)O(1) lookup, insertion and deletion.
  • Keys/elements must be hashable (implement __hash__ and __eq__ consistently; equal objects must have equal hashes). Mutable built-ins are unhashable.
  • Since Python 3.7, dicts preserve insertion order.
  • collections.Counter and defaultdict are dict subclasses for counting and grouping.
Operationlistset / dict
x in sO(n)O(n)O(1)O(1) average
insertO(1)O(1) at endO(1)O(1) average
delete by value/keyO(n)O(n)O(1)O(1) average
ordered iterationyesdict: insertion order; set: no order

Hashing patterns in algorithms

Hash tables vs balanced BSTs: hashing gives O(1)O(1) expected but no ordering; BSTs give O(log⁡n)O(\log n) guaranteed plus sorted iteration, range queries, min/max and predecessor/successor.

Quick revision

Practice questions

GATE-style questions: 3 one-mark and 6 two-mark. Wrong MCQs cost ⅓ of their marks in the real exam; MSQ and NAT have no negative marking. Attempt each before opening the solution.

Q1NAT2 marks

Keys 10, 17, 24, 3 are inserted in this order into an initially empty hash table of size 7 using h(k)=k mod 7h(k) = k \bmod 7 and linear probing. The index at which key 3 is stored is ______.

Q2MCQ1 mark

With separate chaining and simple uniform hashing, the expected time for a search in a table with load factor α=n/m\alpha = n/m is

Q3NAT2 marks

Under the uniform hashing assumption, the expected number of probes in an unsuccessful search in an open-addressing table with load factor α=0.5\alpha = 0.5 is at most ______.

Q4NAT2 marks

Keys 22, 33, 44 are inserted in order into an empty table of size 11 using quadratic probing h(k,i)=(k+i2) mod 11h(k, i) = (k + i^2) \bmod 11 for i=0,1,2,…i = 0, 1, 2, \dots. The index of key 44 is ______.

Q5MSQ2 marks

Which statements about collision resolution are correct?

One or more options are correct.

Q6MCQ1 mark

Which of these can be used as a key in a Python dict?

Q7NAT2 marks

20 keys are hashed independently and uniformly into 100 slots. The expected number of colliding pairs of keys (pairs that land in the same slot) is ______.

Q8NAT1 mark

Double hashing uses h(k,i)=(h1(k)+i h2(k)) mod 13h(k, i) = (h_1(k) + i\,h_2(k)) \bmod 13 with h1(k)=k mod 13h_1(k) = k \bmod 13 and h2(k)=1+(k mod 11)h_2(k) = 1 + (k \bmod 11). For k=27k = 27, the slot probed at i=1i = 1 (after a collision at i=0i = 0) is ______.

Q9NAT2 marks

What does this program print?

Python
seen = set()
pairs = 0
for x in [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]:
    if 10 - x in seen:
        pairs += 1
    seen.add(x)
print(pairs)