# PaCHash: Packed and Compressed Hash Tables

arXiv: https://arxiv.org/abs/2205.04745 · HTML: https://mlsanity.com/paper/2205.04745/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 May 2022.

## Built on by (most cited first, 1 of 1)

- [Learned Static Function Data Structures](https://mlsanity.com/paper/2510.27588/) (2025)

## Abstract (arXiv)

We introduce PaCHash, a hash table that stores its objects contiguously in an array without intervening space, even if the objects have variable size. In particular, each object can be compressed using standard compression techniques. A small search data structure allows locating the objects in constant expected time. PaCHash is most naturally described as a static external hash table where it needs a constant number of bits of internal memory per block of external memory. Here, in some sense, PaCHash beats a lower bound on the space consumption of k-perfect hashing. An implementation for fast SSDs needs about 5 bits of internal memory per block of external memory, requires only one disk access (of variable length) per search operation, and has small internal search overhead compared to the disk access cost. Our experiments show that it has lower space consumption than all previous approaches even when considering objects of identical size.