Succinct and Fast Tiny Pointer Hash Tables
For systems relying on hash tables, TPHT advances the latency-space Pareto frontier, offering production-ready designs that reduce memory usage without sacrificing performance.
The paper introduces Tiny Pointer Hash Tables (TPHT), a family of hash tables that compress pointers and keys to reduce memory overhead while maintaining fast operations. Chained-TPHT achieves 105.4% space efficiency (footprint less than data size) and Flattened-TPHT achieves 83.4% space efficiency with up to 89.3% higher throughput than strong baselines.
Hash tables sit on the critical path of many systems, yet modern designs still force a trade-off between fast operations and high memory overhead. We revisit this trade-off and present Tiny Pointer Hash Tables (TPHT), a family of practical hash tables that make two ideas from theory work at system scale: compressing pointers down to a byte, and encoding keys compactly so less metadata is needed. We engineer these ideas into two complementary designs. Chained-TPHT targets maximal space savings, and is to the best of our knowledge the first simple and practical succinct hash table design, achieving a footprint less than the total data size with constant-time operations. Flattened-TPHT targets latency, organizing data to keep the common case within a single cache miss while retaining strong space efficiency. Both variants support dynamic resizing without global pauses and integrate cleanly with 64-bit keys and values. Across YCSB and microbenchmarks, TPHT advances the latency-space Pareto frontier: Chained-TPHT reaches 105.4% space efficiency, and Flattened-TPHT achieves 83.4% space efficiency with up to 89.3% higher throughput than strong baselines. Together, these results show that techniques primarily known in theory can be turned into production-ready hash tables that meaningfully reduce memory use while delivering state-of-the-art performance.