Succinct and Fast Tiny Pointer Hash Tables

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 into two complementary designs. Chained-TPHT targets maximal space savings, and is to our knowledge the first simple and practical succinct hash table, achieving a footprint smaller than the raw key-value payload size with constant-time operations. Flattened-TPHT targets latency, keeping 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 systems-ready hash tables that meaningfully reduce memory use while delivering state-of-the-art performance.