Catalan Hashing: Efficient Linear Probing for Variable-Length Items

A defining feature of the linear-probing hash table is its spatial locality: at load factor 1 - ε, the hash table can be implemented so that each operation scans a single contiguous region of expected size O(1/ε) (this is known as the scan cost). This guarantee, however, relies on all items having unit size. In this paper, we ask whether it is possible to achieve a similar guarantee, but in a hash table that stores items of arbitrary lengths |x| ≥ 1. The main result of the paper is a new hash table called Catalan hashing, which supports amortized expected scan cost O(|x|/ε) for positive queries, O(1/ε) for negative queries, and O(|x|ε⁻¹log1+δ|x|) for insertions/deletions, for any constant $δ> 0$. As a corollary, we obtain the same bounds in the cache-oblivious model, with a scan cost of S translating to $1 + O(S/B)$ I/Os. Along the way, we introduce several high-level techniques that may be of independent interest; this includes a novel way of using erasure codes in order to perform write optimization within a hash table, and a connection to scheduling that allows us to place elements in a way which avoids clustering at high load factors.