Succinct and Fast Tiny Pointer Hash Tables

Abstract

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.

Comments: 16 pages, 13 figures. Author-prepared arXiv version of the PVLDB paper. Source code and experimental artifacts: https://github.com/Xilinion/TinyPtr . Standalone implementation for direct use: https://github.com/Xilinion/TPHT