Skip to content
AEVROFY
Data Structures & Algorithmsbeginner · 40 min

Hash Tables

Prerequisites: Arrays & Strings

Average O(1) insert/lookup/delete by mapping keys to buckets via a hash function. Understand collisions, load factor, and why worst-case is O(n) — the structure behind most 'do it in one pass' tricks.

How they work

A hash function maps a key to a bucket index. Good hashing distributes keys uniformly so most buckets hold ~one item, giving O(1) average operations. JS Map/Object, Python dict/set, and Java HashMap are all hash tables.

Collisions & load factor

Two keys can hash to the same bucket. Chaining stores a list per bucket; open addressing probes for the next free slot. As the load factor (items / buckets) rises, collisions increase, so tables resize (rehash) to keep operations fast — which is why worst-case is O(n).

Resources

Practice & test yourself

Take the quiz →

Code challenges