Hash tables

O(1) lookup by any key: hash it to a bucket. The structure behind every dictionary.

The idea, and the catch

• Hash the key → integer → bucket index (mod capacity)
• Go straight to the slot — no scanning
• Collisions are inevitable; two ways to handle them:
  • Chaining: a list per bucket
  • Open addressing: probe to the next free slot

Watch collisions form chains

3, 11, 19 all hash to bucket 3 → a chain of three. Lookup scans just that short chain.

The load factor is the dial

$\alpha = n/m$ — items per bucket

• Chaining: expected chain length $\alpha$ → $O(1+\alpha)$
• Probing: probes ~ $\tfrac{1}{2}(1 + \tfrac{1}{1-\alpha})$
• Resize to keep α bounded → O(1). Worst case O(n).

Scratch vs library

Open addressing beats chaining (cache). dict beats both (C). All O(1).

Takeaway

Average O(1) get/put/delete — as long as the load factor stays bounded. No order, though. Next: the hash function itself.