Noesis
3.3.2Hashing

Hash table — structure, open addressing vs chaining

2,060 words9 min readdifficulty · medium3 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHY does a hash table exist?

WHAT is the core structure?

Figure — Hash table — structure, open addressing vs chaining

HOW does the hash function turn a key into an index?

A classic string hash (polynomial rolling hash):

hcode(s)=(∑i=0L−1si⋅p L−1−i),index=hcode(s) mod mh_{\text{code}}(s) = \Big(\sum_{i=0}^{L-1} s_i \cdot p^{\,L-1-i}\Big), \qquad \text{index} = h_{\text{code}}(s) \bmod m

Collisions are inevitable — WHY?

Strategy 1: Separate Chaining

Cost: average list length =α=\alpha, so expected search =O(1+α)=O(1+\alpha).

Strategy 2: Open Addressing

Probing f(i)f(i) Problem
Linear ii primary clustering (long runs grow)
Quadratic i2i^2 secondary clustering; may miss slots
Double hashing i⋅h2(k)i\cdot h_2(k) best spread; needs 2nd hash

WHY a low load factor matters

Chaining vs Open Addressing — the 80/20 decision table

Chaining Open addressing
Storage array + lists (extra pointers) one flat array (cache-friendly)
Load factor can exceed 1 must stay <1<1
Deletion trivial (unlink) needs tombstones
Worst case O(n)O(n) (all in one list) O(n)O(n) (long probe run)
Cache poor (pointer chasing) excellent
Best when many deletes, unknown nn speed-critical, α\alpha controlled

Flashcards

What is the load factor of a hash table?
α=n/m\alpha = n/m, stored items divided by capacity.
Why are collisions unavoidable?
Pigeonhole — infinite possible keys, finite mm slots, so two keys must share a slot.
In separate chaining, what does each bucket store?
A linked list (or small structure) of all keys that hashed to that bucket.
Expected unsuccessful-search probes in open addressing?
11−α\frac{1}{1-\alpha}.
Why must open addressing use tombstones on deletion?
An emptied slot would stop later searches early, severing the probe chain; a tombstone says "keep probing" but "free to reuse".
What is primary clustering?
Long contiguous runs of filled slots forming under linear probing, lengthening future probes.
Linear vs quadratic vs double-hashing probe function f(i)f(i)?
ii vs i2i^2 vs i⋅h2(k)i\cdot h_2(k).
Why choose prime p=31p=31 in a polynomial string hash?
Prime > alphabet size spreads bits; and 31x=(x ⁣≪ ⁣5)−x31x=(x\!\ll\!5)-x is cheap.
When do you rehash and what happens?
When α\alpha exceeds a threshold; allocate a bigger array (≈double) and reinsert all keys.
Average search cost in chaining?
O(1+α)O(1+\alpha).
Why does a simple character sum make a bad string hash?
Anagrams like "ab"/"ba" collide; order is ignored.
Open addressing's main hardware advantage over chaining?
Cache friendliness — data is contiguous, no pointer chasing.
Recall Feynman: explain it to a 12-year-old

Imagine a row of numbered lockers. Instead of searching every locker for your bag, you have a magic rule that says "your bag goes in locker number 7" just by looking at your name. Super fast! But sometimes two kids' names point to the same locker — that's a collision. Two fixes: (1) Chaining — put a little bag-rack inside locker 7 and hang both bags there. (2) Open addressing — if locker 7 is taken, just walk to the next free locker (8, 9, ...) and remember to walk the same way when you come back. If lockers get too crowded, you rent a bigger hallway and move everyone — that's rehashing.

Connections

  • Hash functions — properties and design
  • Polynomial rolling hash & Rabin–Karp
  • Load factor and dynamic resizing / rehashing
  • Linked lists (chaining buckets)
  • Amortized analysis (why resizing stays O(1)O(1))
  • Birthday paradox (collision frequency)
  • Sets and Maps / Dictionaries (built on hash tables)

Concept Map

input to

stage 1 produces

stage 2 via

yields

selects slot in

fullness measured by

pigeonhole forces

resolved by

resolved by

bucket holds linked list

high alpha degrades

Key like banana

Hash function h

Hash code integer

Compression mod m

Index in array

Buckets array size m

Load factor n over m

Collision h k1 equals h k2

Separate chaining

Open addressing

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho hash table ek bada array hai jisme har key ka address hum calculate karte hain, dhoondte nahi. Yeh kaam karti hai hash function — key (jaise string "banana") ko ek number me badalti hai, phir % m karke valid index nikal lete hai. Isliye average me search, insert, delete sab O(1)O(1) ho jaata hai. Lekin problem yeh hai ki do alag keys kabhi-kabhi same slot par aa jaati hain — isko collision kehte hai, aur pigeonhole principle ke wajah se yeh hona hi hona hai.

Collision handle karne ke do tareeke hai. Chaining me har bucket ke andar ek chhoti linked list hoti hai — jitni keys same slot par aayi, sab us list me ad hoti jaati hai. Open addressing me sab keys array ke andar hi rehti hai; agar slot bhara hai to agle khaali slot tak probe (chalte) karte hai — linear probing me +1,+2,+3+1, +2, +3 aage badhte ho. Yaad rakho: search ke time bhi wahi probe sequence follow karna padta hai jo insert ke time follow kiya tha.

Ek important trap: open addressing me delete karte waqt slot ko seedha khaali mat karo, warna baad ki searches beech me ruk jaayengi. Iske liye tombstone (DELETED marker) lagao. Aur load factor α=n/m\alpha = n/m ko control me rakhna zaroori hai — open addressing me unsuccessful search ka expected cost 11−α\frac{1}{1-\alpha} hota hai, yaani 90% bhara hua table me ~10 probes lagte hai. Isliye α\alpha jab limit cross kare to rehash karo: bada array banao aur sab keys dobara daalo. Yehi cheez interviews aur real systems (HashMap, dict, unordered_map) ka core hai.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 2,952 wordsD2Visual walkthroughThe derivation in pictures · 3,002 wordsD3Worked examplesEvery scenario covered · 2,552 wordsD4ExercisesGraded, full solutions · 2,664 wordsD5Question bankConcept traps, quick reveals · 1,618 words

Test yourself — Hashing

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

Amortized analysis — aggregate, accounting, potential methodsCoding · 3.1.5Array — static, dynamic; cache locality; amortized O(1) appendCoding · 3.2.1Hash function — properties - deterministic, uniform, fastCoding · 3.3.1Trie (prefix tree) — insert, search, startsWith, applications (autocomplete, spell check)Coding · 3.4.14