Designing Hash Tables Optimised for CPU Cache Hierarchy

Memory hierarchy effects are increasingly taking precedence over algorithmic complexity in determining hash table performance on contemporary processors. Existing surveys address hashing methods and collision resolution algorithms, yet no single cache-centric framework fully explains why different architectures exhibit performance variability. This paper presents a taxonomy of hash table design options based on cache behavior, encompassing memory layout strategies, collision resolution techniques, probing patterns, and metadata organization. We synthesize prior research to identify key performance drivers and failure modes, demonstrating why open-addressing and SIMD-friendly architectures achieve superior cache utilization while pointer-intensive chaining methods suffer from poor locality. We further identify promising research directions, including vectorized lookup acceleration, adaptive probing, cache-line-aware resizing, and NUMA-conscious hashing.