Hash Tables: Dictionary and Set Implementation with Hash Functions
Hash tables are among the most versatile and widely used data structures in computer science. They provide average O(1) time for insertions, deletions, and lookups — making them indispensable for databases, compilers, caches, and countless other applications. Understanding their internals is essential for writing efficient code and debugging performance issues in production systems.
Hash Functions: The Foundation
A hash function maps a key to an integer index within the table. The quality of the hash function directly determines hash table performance — a poor hash function causes clustering and degrades lookup time from O(1) to O(n).
Properties of Good Hash Functions
A good hash function is deterministic — the same key always produces the same hash. It provides uniform distribution across buckets. It is efficient to compute. And it minimizes collisions even when keys share patterns — for example, consecutive integers should not all fall into consecutive buckets.
String Hashing
Simple string hash functions sum character codes or use polynomial hashing with a base and modulus:
hash(s) = (s[0] × B^(n-1) + s[1] × B^(n-2) + … + s[n-1]) mod M
A common choice is B = 31 and M = 2^32 or a large prime, as used by Java’s String.hashCode(). The choice of 31 is empirical — it provides good distribution while being computable as (x « 5) - x, a single-cycle CPU operation. Python’s SipHash combines speed with cryptographic security against hash-flooding denial-of-service attacks.
Cryptographic vs Non-Cryptographic Hash Functions
Non-cryptographic hash functions prioritize speed over security. FNV-1a, MurmurHash3, xxHash, and CityHash are popular choices for hash tables. They run at 10-50 GB/s on modern hardware.
Cryptographic hash functions like SHA-256 and BLAKE3 are far too slow for hash tables — they prioritize collision resistance against adversarial inputs over raw throughput. The recent rise of hash-flooding attacks has led languages to adopt randomized hash seeds per process invocation, making C++ unordered_map and Python dict resistant to worst-case degradation.
Collision Resolution Strategies
Collisions occur when two keys hash to the same index. Two main strategies handle this situation, each with distinct trade-offs.
Chaining
Each bucket stores a linked list (or balanced tree in high-collision scenarios) of key-value pairs. On lookup, the table hashes the key, locates the bucket, and traverses the list to find the matching key.
Chaining handles high load factors gracefully — performance degrades linearly rather than catastrophically. Insertion always succeeds without probing. However, pointers in linked lists consume extra memory, and following pointer chains causes cache misses. Java’s HashMap switches from linked lists to red-black trees when a bucket exceeds 8 entries, providing guaranteed O(log n) performance for pathological hash distributions.
Open Addressing
When a collision occurs, open addressing probes for the next available slot. All data lives in the table array itself, eliminating pointer overhead and improving cache performance.
Linear Probing: Check successive slots. Simple to implement and maximally cache-friendly — the CPU can prefetch adjacent cache lines. However, linear probing suffers from primary clustering, where collisions form contiguous blocks that increase probe lengths for subsequent insertions.
Quadratic Probing: Check slots at increasing intervals (1, 4, 9, 16…). Reduces clustering compared to linear probing but may not find an empty slot even if one exists. Guaranteed to find a slot only when the load factor is below 0.5 and the table size is prime.
Double Hashing: Use a second hash function for the probe interval. Provides the best distribution of open addressing strategies. The probe sequence is essentially random, minimizing both primary and secondary clustering.
The choice between chaining and open addressing has been debated for decades. Google’s Abseil flat_hash_map uses open addressing with SwissTable SIMD probing, achieving 2-3x speedup over traditional chaining implementations. Python’s dict uses open addressing with pseudo-random probing.
Load Factor and Dynamic Resizing
The load factor α = n / m (number of elements divided by table size) controls the time-memory trade-off. Lower load factors reduce collisions but waste memory. Higher load factors use memory efficiently but increase probe lengths.
Resizing Thresholds
Java’s HashMap resizes at α = 0.75. Python’s dict resizes at approximately α = 2/3. C++ unordered_map’s default max_load_factor is 1.0 (GCC) or 0.75 (Clang). Google’s dense_hash_map requires the load factor to stay below 0.5 for guaranteed O(1) operations.
Resizing allocates a new table (typically 2x the current size) and rehashes all existing entries — an O(n) operation. The amortized analysis shows that the average cost per insertion remains O(1) because resizing happens infrequently.
Implementing Dictionaries and Sets
A dictionary (map) associates unique keys with values. The standard implementation uses a hash table with key-value pair entries. When inserting, the table computes the hash, resolves collisions, and stores the entry. Lookup repeats the process and returns the associated value.
Sets store unique keys without values. They share the same hash table implementation but omit the value field. Set operations — union, intersection, difference — run in O(min(n, m)) when implemented with hash tables.
Language-Specific Implementations
Python’s dict is the most optimized hash table in widespread use. It stores entries in a compact array of hashes, indexes, and key-value pairs. Memory overhead is approximately 30% for typical workloads. In Python 3.7+, dict preserves insertion order as a language guarantee.
Java’s HashMap uses chaining with an array of Node objects. It supports null keys and is not thread-safe. ConcurrentHashMap uses striped locking for concurrent access without full-table synchronization.
C++ std::unordered_map provides standard hash table semantics but is famously slow due to mandatory pointer-based buckets. The Abseil flat_hash_map provides a faster alternative with open addressing and SIMD probing.
Go’s map[T]U is built into the language with hardware-specific optimizations. It provides O(1) average-case performance and returns the zero value for missing keys.
Advanced Hash Table Internals
Robin Hood Hashing
Robin Hood hashing is an open-addressing variant that reduces probe length variance. When inserting a key, if the current slot is occupied by a key with a shorter probe distance, the algorithm swaps — the new key takes the slot and the displaced key continues probing. This equalizes probe lengths: all keys have approximately the same search cost, eliminating long-tail latency.
Rust’s HashMap uses Robin Hood hashing. The technique significantly improves worst-case lookup performance at the cost of slightly more expensive insertions.
SwissTable and SIMD Acceleration
Google’s SwissTable (used in Abseil’s flat_hash_map) groups buckets into 16-entry groups, each with a 16-byte metadata array using one byte per slot. The metadata byte stores the 7-bit hash prefix and a status bit (empty, occupied, or deleted). Lookups use SSE2/AVX2 instructions to compare all 16 metadata bytes simultaneously — a single CPU instruction searches 16 buckets in parallel.
SwissTable achieves 2-3x throughput improvement over traditional chaining implementations. The technique is now adopted in LLVM’s DenseMap and Rust’s hashbrown library.
Cuckoo Hashing
Cuckoo hashing uses two independent hash functions and two tables. On insertion, place the key in the first table at h1(key). If that slot is occupied by key2, kick key2 out and insert it in the second table at h2(key2). If that slot is also occupied, kick that key out recursively. The process converges quickly with sufficiently large tables.
Cuckoo hashing guarantees O(1) worst-case lookup with at most two memory accesses. It is used in high-performance networking and packet processing applications where predictable latency is critical.
Frequently Asked Questions
What happens when a hash table becomes full?
The table resizes — typically doubling its capacity and rehashing all existing entries. Before resizing, the load factor exceeds the threshold, triggering allocation of a new, larger table. The resize operation is expensive (O(n)) but amortizes to O(1) per insertion.
Why do hash tables provide O(1) lookup but only on average?
Worst-case behavior occurs when all keys hash to the same bucket. With chaining, lookup degrades to O(n). With open addressing, probe sequences can become very long. Good hash functions and randomized seeds make worst-case inputs vanishingly unlikely for non-adversarial use.
How should I choose a hash function for my custom data type?
Combine the hash values of all fields using a well-known mixing function. For example, in C++: boost::hash_combine: hash ^= hash_field + 0x9e3779b9 + (hash << 6) + (hash >> 2). Avoid simple XOR of field hashes, which produces zero for equal fields and symmetric results for permuted fields.
What is a perfect hash function?
A perfect hash function maps n keys to n distinct integers with zero collisions. Minimal perfect hash functions map to n consecutive integers. They are constructed offline for known key sets and are used in compilers (keyword recognition), databases (primary key indexes), and routing tables.
How does a hash table differ from a binary search tree?
Hash tables provide O(1) average lookup but no ordering guarantee. BSTs provide O(log n) lookup with sorted-order traversal and range queries. Hash tables are faster for equality lookups; BSTs are better when order matters or when worst-case performance guarantees are required.