Hash Tables That Fit Below Their Own Data: Pointers, Squeezed to a Byte
Tiny Pointer Hash Tables (TPHT) compress pointers down to a byte and encode keys compactly, so a hash table's footprint can dip below the size of the data it holds. Chained-TPHT hits 105.4% space efficiency, while Flattened-TPHT keeps the common case to one cache miss and runs up to 89.3% faster than strong baselines. Both resize dynamically without global pauses and work with standard 64-bit keys. It's a rare case of theory-turned-practical data structures advancing the latency-space frontier.