Why it matters
Hash tables underpin caches, indexes, and countless algorithms. Understanding when their O(1) becomes O(n) — bad hash function, high load factor, adversarial keys — is critical.
The architecture
Hash function: maps keys to bucket indices. Good hash functions distribute keys uniformly. Bad hash functions cluster keys, degrading performance.
Collision: two keys hash to same bucket. Resolved via chaining (linked list per bucket) or open addressing (probe for next empty slot).
How it works end to end
Chaining: each bucket holds a linked list of entries. Simple, tolerates high load factor, per-entry pointer overhead.
Open addressing: probe sequences (linear, quadratic, double hashing) to find empty slot. Cache-friendly, harder to delete correctly.
Robin Hood hashing: variant of open addressing that minimizes worst-case probe length.
Load factor: entries / buckets. Beyond ~0.7 for open addressing or ~1 for chaining, resize by doubling.