Hash Tables
A hash table is a data structure that maps keys to values using a hash function. It offers average O(1) insertion, deletion, and lookup — one of the most powerful trade-offs in computing.
Hash Functions
A good hash function should be:
- Deterministic: Same key always produces the same hash.
- Uniform: Distributes keys evenly across the table.
- Fast: O(1) to compute.
- Non-invertible: Hard to recover the key from the hash (for cryptographic hashes).
Collision Resolution
When two keys hash to the same index:
1. Separate Chaining: Each bucket holds a linked list (or balanced tree) of entries. Collisions just add to the list.
| Operation | Average | Worst |
|---|---|---|
| Search | O(1 + α) | O(n) |
| Insert | O(1) | O(1) |
| Delete | O(1 + α) | O(n) |
α = load factor = n/m (number of entries / number of buckets)
2. Open Addressing: All entries are stored in the table itself. On collision, probe for the next empty slot.
| Probe Strategy | Description |
|---|---|
| Linear probing | Try index+1, index+2, … (simple but causes clustering) |
| Quadratic probing | Try index+1², index+2², … (reduces clustering) |
| Double hashing | Use a second hash function for step size (best distribution) |
Load Factor & Resizing
- When load factor exceeds a threshold (typically 0.75), the table is resized — typically doubled in size and all entries are rehashed.
- Rehashing is O(n) but amortized O(1) per insertion.
Applications
- Symbol tables in compilers and interpreters
- Database indexing (hash indexes)
- Caching (memcached, Redis)
- Associative arrays (Python dict, JavaScript Map, Java HashMap)
- Set membership (HashSet)
- Deduplication and counting (histograms, frequency maps)