Hash tables are the most-used data structure in software. They give O(1) average lookup, insert, delete. The "average" hides important engineering decisions.
Understanding hash table design helps you use them well, avoid pathological cases, and know when to use alternatives.
Insert: hash key, place in slot. Lookup: hash key, check slot. Delete: hash key, remove from slot.
A good hash function:
For application use: language standard library hash. Don't roll your own.
SHA-256 etc. Overkill for hash tables (slow). Use only when adversarial inputs matter.
Two main strategies:
Each slot is a linked list (or other structure). Collisions append to list.
Pros:
Cons:
When slot is full, probe to find empty slot.
Probe sequences:
Pros:
Cons:
Open addressing variant. When inserting, if you encounter a record with smaller probe distance, swap.
Equalizes probe distances. Practical and fast.
Two hash functions; each key has two possible slots. Insert: place in either; if both occupied, evict and reinsert.
Worst-case O(1) lookup. Insertion can fail (need rehash).
Combines open addressing with bounded distance. Each key within H slots of its ideal position.
Load factor α = filled slots / total slots.
Performance vs load factor depends on strategy:
When load factor exceeds threshold, resize the table (double capacity, rehash all keys).
Single resize: O(n). Amortized over insertions: O(1).
For latency-sensitive applications: rehash a few entries per operation rather than all at once.
Used in Redis.
Chaining. Treeifies long chains for worst-case O(log n).
Default load factor 0.75.
Chaining. Often slower than alternatives due to spec constraints.
Many use absl::flat_hash_map or robin_hood instead.
Open addressing with perturbation-based probing.
Insertion-ordered since Python 3.7.
Open addressing variant. Uses 8-key buckets for cache locality.
SipHash by default (DoS-resistant). Open addressing (Robin Hood-style).
Open addressing wins for cache. Each probe is contiguous memory.
Chaining: pointer chasing, cache misses.
Linear probing has predictable access patterns.
Bad hash → many collisions → terrible performance.
Test hash quality with key distribution from production.
Pack data tightly. Group hot fields. Avoid pointer indirection.
absl::flat_hash_map is fast partly because it stores keys+values inline.
Adversary submits keys all hashing to same slot. Hash table degrades to linked list.
Mitigations:
Many languages randomize hash seeds by default. Some still vulnerable.
Use a tree (TreeMap, std::map).
Hash tables have O(n) worst case. For real-time systems, may not be acceptable.
Hash tables can't do range queries. Use trees.
For small N (<10-20), linear search is faster.
If keys change, hash tables break.
Multiple threads access simultaneously.
Lock-free designs exist but are complex.
Update returns a new map; old map unchanged.
Used in functional languages (Clojure, Scala).
Hash array mapped tries (HAMT) are a common implementation.
Probabilistic. Tells you "definitely not" or "maybe yes."
Useful for cache filters: skip expensive lookup if Bloom says no.
Like Bloom but supports deletion.
Probabilistic counting. For analytics, frequency estimation.
Empty hash table: pointer + size + capacity. Tens of bytes.
Per entry:
Open addressing typically lower per-entry overhead.
Random-seeming functions often have bad distribution. Use library hashes.
Hash changes; key unfindable.
Hash tables resize, but resizing during a critical path causes latency spikes.
User-supplied keys without DoS-resistant hash.
Default usually fine; tune only with measurement.
Behavior is implementation-specific. Often UB or exception.
For most application code:
When you do need to optimize: