A hash table trades a little memory and some careful design for one of the most useful promises in computing: finding a value by its key in expected constant time.
The core idea
A hash function turns a key into a number. That number, reduced to fit the table size, selects a slot in an array. To look up "Maria", the program computes the hash, jumps straight to a slot, and checks what is stored there. Nothing has to be scanned from the beginning.
Collisions are normal
Two different keys can land in the same slot. Good tables expect this and handle it. Chaining keeps a small list in each slot. Open addressing probes for the next free slot. Both approaches work well as long as the table does not become too crowded.
Load factor and resizing
The load factor is the number of stored items divided by the number of slots. As it rises, collisions become more common and operations slow down. Most implementations resize, often by doubling the array, once the load factor crosses a threshold, and then reinsert every item. The rebuild is expensive but rare, so the average cost per insert stays low.
What to remember
- Lookup, insert, and delete are O(1) on average, but can degrade to O(n) when many keys collide.
- Hash tables do not keep keys in sorted order. For ordered traversal or range queries, a balanced tree is a better fit.
- Keys must be hashable and must not change while they are stored.
When to reach for one
Use a hash table when the question is "have I seen this before?", "how many times?", or "what is the value for this key?" Counting words, caching results, and detecting duplicates are all natural fits.
Continue with the book
Explore the full treatment, worked examples, and exercises in Algorithms Made Simple.
Adapted from Algorithms Made Simple, published by Choral Software. Article text and original examples © 2026 Choral Software. All rights reserved.