← Back to the hash tables page
Separate Chaining
Each bucket holds a small list of entries that share a hash. Simple, tolerant of high load factors, and easy to delete from.
What to know
- Load factor = entries / buckets; chains average that length under a good hash.
- Java HashMap converts long chains (≥ 8) into red-black trees to cap worst case at O(log n).
- Resizing rehashes every entry into a doubled bucket array.
In the wild: Java HashMap, Python dict history, most textbook implementations.
Algorithms to reach for
Hash + chain walk
O(1) avg, O(chain) worstInsert/lookup/delete under collisions
Treeify long chains
O(log n) worstDefend against hash-flood attacks
Practice problems — with full guides
Each problem has its own page: progressive hints, how to approach it, and the full solution.