Hash Tables
A hash table maps keys to slots through a hash function, delivering expected constant-time insertion, lookup, and deletion.
From key to slot
A hash table stores key-value pairs in an array of buckets. A hash function turns a key into an integer, and that integer modulo the array size selects a bucket. Because the function computes the location directly, lookups do not scan: the expected cost of insert, find, and delete is O(1).
The load factor
Performance depends on the load factor, the ratio of stored entries to buckets. As it rises, collisions become more frequent and operations slow. Implementations keep the load factor below a threshold (often around 0.75) by rehashing: allocating a larger bucket array and reinserting every entry, an O(n) operation amortized to O(1) per insert.
- Insert: O(1) expected, O(n) worst case
- Lookup: O(1) expected, O(n) worst case
- Delete: O(1) expected
- Ordered traversal: not supported — use a tree instead
Two ways to resolve collisions
When two keys land in the same bucket there is a collision. Separate chaining stores a linked list (or small tree) in each bucket. Open addressing keeps everything in the array and probes to a nearby free slot on collision. Both are covered in depth on the collisions page.
What a good hash function does
A good hash spreads keys uniformly across buckets so no slot is overloaded, computes fast, and is deterministic. Poor hashing that clusters keys degrades every operation toward the O(n) worst case. Adversarial inputs can force worst-case behaviour deliberately, which is why some libraries randomise their hash seed.
Trade-offs versus trees
Hash tables beat balanced trees on raw lookup speed but give no order: you cannot ask for the smallest key or iterate in sorted order cheaply. When ordered queries matter, a balanced search tree with O(log n) operations is the right choice.