Hash Tables

Hashing · Collisions · O(1)

1:00

How hash tables compute where a value lives instead of searching for it, achieving O(1) average-case lookup through hashing, collision resolution, and load-factor management.

By the end, you can

Explain why a hash table finds values faster than a linear scan.
Compute a bucket index using the division method `key % m`.
Define collision and explain why collisions are mathematically unavoidable.
Contrast separate chaining with open addressing, including their trade-offs.
Calculate load factor and identify when a resize should be triggered.
State the average-case O(1) and worst-case O(n) complexity and explain what causes each.
Recognize that hash tables are unordered and know which situations require a different structure.
Name real-world uses of hash tables: dictionaries, sets, caches, and database indexes.

Up next in Trees, Hashing & Graphs