Hash Table Search

Hash Function · Collisions · Load Factor

1:00

How a hash table computes a key's address directly — achieving average O(1) lookup — and how collisions, chaining, open addressing, and load factor control its performance.

By the end, you can

Explain why a hash table achieves average O(1) search while linear search is O(n) and binary search is O(log n).
Compute a slot index from a hash code using the modulo formula.
Describe the three required properties of a good hash function.
Explain what a collision is, why it is unavoidable, and how separate chaining and open addressing each resolve it.
Calculate the load factor and identify when a table should be resized.
Describe the rehashing process and why old indices cannot simply be copied to the new array.
Distinguish the O(1) average case from the O(n) worst case and state what keeps a table in the average case.

Up next in Searching & Sorting