Catalan Hashing: Efficient Linear Probing for Variable-Length Items

Introduction

First introduced in the 1950s [48, 35], the linear-probing hash table has stood for more than half a century as one of the simplest and most widely used hash table designs. In its most basic form, the hash table works as follows. Elements live in an array of some size $m$, and each element $x$ hashes to a uniformly random position $h(x)$ in that array. To insert an item $x$, we examine cells $h(x), h(x) + 1, h(x) + 2, \ldots$ (mod $m$) until we find a free cell where we place the item; and, likewise, to query an item $x$, we scan the cells $h(x), h(x) + 1, h(x) + 2, \ldots$ (mod $m$) and until we either find $x$, or until we encounter a free cell (meaning that $x$ is not present).

What makes linear probing special—both in practice and in theory—is its spatial locality [37, 44, 14, 16, 24, 50]: each operation accesses just one small contiguous region of the hash table. We refer to the size of this region as the scan cost of the operation. (This quantity has also been called the locality of the operation [57]).

At constant load factor $1 - \Theta(1)$, the expected scan cost per operation is $O(1)$. When the hash table is filled to a high load factor $1 - \varepsilon$ for a small parameter $\varepsilon\in(0,1)$, naive linear probing suffers from a phenomenon known as primary clustering [35, 38, 37], which increases the worst-case expected scan cost to $\Theta(\varepsilon^{-2})$. Fortunately, this clustering effect can actually be eliminated with the help of additional algorithmic optimizations (the use of the Robin-Hood ordering to improve queries [3, 19] and the use of graveyard hashing [14] to improve insertions). With these optimizations in place, the expected scan cost per operation is $O(\varepsilon^{-1})$.

The above results all operate under the assumption that items have a fixed size. In many applications, however, this is not the case: An item $x$ may occupy an arbitrary number $|x| \ge1$ of words (representing, for instance, a variable-length key together with a variable-length value). A common workaround is to use indirection: store a fixed-size pointer in the hash table and allocate the item itself elsewhere in memory. But indirection defeats the very spatial locality that makes linear probing so desirable—each operation must now access multiple separate regions of memory.

This raises a natural question: Can linear probing be adapted to store variable-length items inline, so that the expected scan cost per query is close to $O(\varepsilon^{-1} \cdot|x|)$, where $|x|$ is the length of the item being queried? In other words, does there exist a data structure that behaves like linear probing, but that supports items of arbitrary sizes?

Such a data structure would also be of direct interest in the external-memory model [1], where memory is divided into blocks of size $B$ and the cost of an operation is the number of blocks it accesses (called I/Os). In this model, a linear-probing operation with scan cost $S$ incurs $1 + O(S/B)$ I/Os in expectation, so bounds on scan cost translate directly into bounds on I/Os. Thus, another way to frame our question is simply: does there exist a cache-oblivious¹ external-memory data structure in which querying an item $x$ costs $1 + O(\varepsilon^{-1}|x|/B)$ I/Os in expectation?

This Paper: Catalan Hashing. In this paper, we introduce Catalan hashing, which successfully extends linear probing to support variable-length items. In the final version of the data structure (Theorem 1.4), we are able to support queries with an amortized expected scan cost of

and insertions and deletions with an amortized expected scan cost of

where $\delta> 0$ is a positive constant of our choice. The query bound applies to both positive queries (for elements that are present) and negative ones (for elements that are absent). In fact, for negative queries, we are able to achieve an even stronger expected scan-cost bound of $O(\varepsilon^{-1})$, independent of the item size $|x|$.

We develop our results systematically in five parts. Parts 1–3 cover static and then dynamic constructions in the constant-load-factor regime (load factor $1-\Theta(1)$). Parts 4–5 then extend these constructions to the high-load-factor regime (load factor $1-\varepsilon$). We state our results in terms of scan cost, which implies corresponding I/O bounds. We state these explicitly here for our final construction and following the theorems in the main text.

Part 1: Simple Catalan Hashing (Static, Low Load Factor). A naive way to store items inline in a linear-probing hash table would be to store each item $x$ as a contiguous block of $|x|$ words starting at or after its hash location $h(x)$. However, as observed by Thorup [54], this can blow up the cost of small items: a single large item of length $L$ occupies $L$ consecutive cells, so an item of length 1 that hashes into that interval is pushed $\Omega(L)$ cells away from its hash location.

In Part 1 (§ 4 and § 5), we introduce (Simple) Catalan hashing, a static linear probing hash table (designed for low load factors $1-\Theta(1)$) that resolves the problem described above. The basic idea is to store items non-contiguously, nesting smaller items inside larger ones. We then augment each cell of the table to store an $O(1)$-bit tag indicating where items begin and end. The items are laid out in such a way that, whenever a smaller item $x$ overlaps a larger one $y$, $x$ is contained entirely within $y$. If one thinks of each tag as encoding either an open parenthesis (starting a new item) or a closing parenthesis (ending the current item), then the tags form a balanced-parentheses sequence (i.e., a Catalan sequence [53]), hence the name of the data structure.

The main result of Part 1 is the following theorem:

Note that the bound for negative queries (queries to keys that are absent) does not even depend on the length $|x|$ of the item being queried. Negative queries make use of the following mechanism: If an item $x$ hashes to some cell $c$, and $x$ is the last item in the table with that hash, then at the end of $x$ we store an $O(1)$-bit tag that indicates this. A negative query for a key $k$ with hash $c$ can therefore stop as soon as it reaches the tag at the end of $x$. Of course, if $x$ is very long, then this could make the query very expensive! Critically, however, long items are necessarily rare (the sum of the lengths of all items is at most the size of the table), so a negative query is unlikely to share its hash with that of a long item. Summing over the items in the table, we show that the expected scan cost of a negative query is just $O(1)$.

Part 2: Write Optimization via Erasure Codes (Dynamic, Low Load Factor). Next, in Part 2, we turn to the question of how to support insertions (deletions are deferred to Part 5). Note that, here, we are still only focusing on hash tables that operate at low load factors—we consider higher load factors in Parts 4 and 5.

Note that naively dynamizing the simple Catalan hash table results in severe write amplification (insertions are very expensive). Suppose, for example, that the table stores a long item $y$ of length $L$, and we insert an item $x$ of length 1 whose hash lands in the middle of $y$. In the static layout, $x$ interrupts $y$, so inserting $x$ requires shifting the remaining $\Omega(L)$ words of $y$ forward, giving the insertion a scan cost of $\Omega(L)$. Worse, if $y$ is itself nested inside an even longer item $y'$, then shifting $y$ forces $y'$ to shift as well, triggering a cascade of updates across items of increasing size.

In the external-memory literature, the classic way to resolve write amplification is to make the data structure write optimized [42, 4, 18, 9, 29, 10, 21]. However, existing write-optimized data structures (such as $B^{\varepsilon}$-trees [18], LSM-trees [42], cache-oblivious streaming B-trees [9], etc.) rely on hierarchical trees of buffers to batch small updates as they trickle down the tree. In a linear-probing hash table, however, there is no tree, and no natural way to add hierarchical buffers in a way that respects spatial locality. Thus, a priori, write optimization would seem to be off the table.

Our solution is a new mechanism for write optimization in linear-probing hash tables: using erasure codes so that large items can themselves act as “buffers” for small items. Instead of storing an item $y$ of length $s = |y|$ directly, we encode $y$ using an erasure code $\operatorname{Enc}(y)$ of length $2s$ from which $y$ can be reconstructed using any $s$ surviving symbols. When a newly inserted short item $x$ needs a cell that is currently occupied by a longer element $y$, $x$ does not move $y$ at all—it simply overwrites $y$’s cell in place. As long as at least $s$ of the $2s$ cells of $\operatorname{Enc}(y)$ survive, any query for $y$ can still decode $y$ in a single contiguous scan, just as before. Only when half of $\operatorname{Enc}(y)$ has been overwritten do we reinflate $y$ by reinserting it as a fresh length-$2s$ codeword; critically, at that point, at least $s = |y|$ words of shorter items have been written on top of $y$, which is enough to amortize the cost of reinflating $y$.

To illustrate the high-level idea behind this technique, we begin in § 6 with a warmup in which we analyze this erasure-coded Catalan hash table under the simplifying assumption that an erasure oracle notifies the algorithm whenever half of an item’s codeword has been overwritten (and supplies the original item to be reinflated). Under this oracle assumption, we prove (Theorem 5.5) that positive queries and insertions both have amortized expected scan cost $O(|x|)$.

Part 3: Removing the Oracle (Dynamic, Low Load Factor). In Part 3 (§ 7), we show how to remove the oracle assumption from Part 2. What makes removing the oracle nontrivial is that, when a short insertion overwrites a cell belonging to a long item $y$, the algorithm cannot, for example, afford to update any counter that is stored at the start of $y$. Because $y$ may be very long, the start of $y$ may lie far before the cell being overwritten, so updating a per-item counter on every overwritten cell would destroy our $O(|x|)$ bound on the scan cost of an insertion. This makes it difficult to identify when an item $y$ has had more than half of its codewords overwritten.

Our solution is to do nothing at all to $y$ when its cells are overwritten, and instead reinflate heavily overwritten items lazily during queries. Whenever an item $x$ is inserted, we also store a backup copy of $x$ in a secondary backup table $\mathcal{B}$ that is interleaved into the same physical array. Most queries for an item $y$ simply find at least $|y|$ surviving symbols of $\operatorname{Enc}(y)$ in the primary table and decode $y$ with scan cost $O(|y|)$. If, however, more than half of $\operatorname{Enc}(y)$ has been overwritten, the query falls back to recovering $y$ from the backup table $\mathcal{B}$ and reinflates $\operatorname{Enc}(y)$ in the primary table.

At first glance, introducing $\mathcal{B}$ might appear to be circular, since $\mathcal{B}$ must itself dynamically store variable-length items. The crucial difference is that a query for $y$ only accesses $\mathcal{B}$ when at least $|y|$ cells of $\operatorname{Enc}(y)$ have been overwritten since $y$ was last inserted or reinflated. We can therefore amortize the cost of querying $\mathcal{B}$ (and reinflating $y$) against the insertions that caused those overwrites. Critically, this means that we can get away with $\mathcal{B}$ supporting slower queries than what we want in the full data structure—it just needs to support all operations with scan cost $O(|x|\log^{1+\delta}|x|)$. The final contribution of Section 6 is to construct a backup table that does just that. Integrating this into the full data structure gives the following theorem:

Part 4: Fair Catalan Hashing (Static, High Load Factors). In Part 4 (§ 8), we move from constant load factors to the high-load-factor regime (load factor $1-\varepsilon$ for some small $\varepsilon\in(0,1)$). To tackle this regime, we begin by returning to the static setting.

At high load factors, simple Catalan hashing ends up encountering the same quadratic barrier as classical linear probing—the worst-case expected scan cost for an item $x$ becomes $\Theta(\varepsilon^{-2}|x|)$. The standard fix in the unit-size setting is to use the Robin Hood hashing [3, 19], which sorts elements in each run in increasing order of hash. But, for variable-length items, this approach fails, because a single long item can blow up the query time of many subsequent short items with larger hashes.

To overcome this obstacle, we establish a connection between variable-length linear probing and preemptive single-server scheduling [51, 33, 32, 6, 5, 26, 28]. If we view each item $x$ as a job of size $|x|$ arriving at time $h(x)$, then we can reinterpret the task of placing the items into the table as a scheduling problem. Under this view, the scan cost of an item $x$ divided by its size $|x|$ is the same as the stretch of the corresponding job.

What we want, then, is a scheduling policy that is fair across all job sizes, guaranteeing worst-case expected stretch $O(\varepsilon^{-1})$. In queuing theory, the simplest such policy is last-in-first-out with preemption, in which newly-arrived jobs immediately preempt any existing jobs. In our hash-table setting, this policy can be viewed as giving priority to items with larger hashes. Note that this prioritization is the exact opposite of the classical Robin Hood ordering [3, 19]. We call the resulting data structure anti-Robin-Hood Catalan hashing (ARCH).

In Section 7, we give a simple, self-contained proof that the ARCH table does, indeed, guarantee an expected scan length of at most $\varepsilon^{-1}|x|$.² Perhaps ironically, this means that the anti-Robin-Hood ordering is actually fairer than its Robin Hood counterpart, once we allow for variable-length items.

We remark that, although the anti-Robin-Hood ordering bounds the expected stretch of every item, which is what we need in Part 5, its expected maximum stretch can be quite large: if the table contains many items of length 2 and a single item of length $L$, then with constant probability the long item preempts one of the short items, giving that item stretch $\Omega(L)$. As an additional result, we show how to bound the expected maximum stretch as well. We adapt the fair-sojourn scheduling protocol of Friedman and Henderson [26] to design a variant of Catalan hashing with expected scan cost at most $1+|x|/\varepsilon$ and expected maximum stretch at most $1+(\ln m+1)/\varepsilon$ (Theorem 7.5).

Part 5: Dynamic Catalan Hashing at High Load Factors

Finally, in Part 5 (§ 9), we combine our static ARCH construction from Part 4 with our dynamic low-load-factor construction from Parts 2 and 3 to obtain a fully dynamic Catalan hash table at load factor $1-\varepsilon$ (supporting both insertions and deletions).

Note that the dynamic erasure-coded hash table from Parts 2 and 3 cannot be run directly at load factor $1-\varepsilon$: its write-optimization machinery inherently loses a constant factor in space. Conversely, the scheduling-based approach from Part 4 achieves load factor $1-\varepsilon$ with only $O(1)$ bits of metadata per cell.

To get the best of both worlds, we use a structure inspired by graveyard hashing [14]. At a high level, we store almost all of the items in a static ARCH table $\mathcal{H}_{\mathrm{full}}$ at load factor $1-O(\varepsilon)$, while routing new insertions into a much smaller dynamic erasure-coded table $\mathcal{H}_{\mathrm{small}}$ of size $O(\varepsilon m)$ that operates at constant load factor. Because $\mathcal{H}_{\mathrm{small}}$ is only a $\Theta(\varepsilon)$ fraction of the size of $\mathcal{H}_{\mathrm{full}}$, its constant-factor space overhead consumes only $O(\varepsilon m)$ cells in total. Moreover, so that an operation that accesses both tables still scans just one small region of memory, we interleave $\mathcal{H}_{\mathrm{small}}$ uniformly into $\mathcal{H}_{\mathrm{full}}$ within a single physical array—placing one slot of $\mathcal{H}_{\mathrm{small}}$ every $\Theta(\varepsilon^{-1})$ slots of $\mathcal{H}_{\mathrm{full}}$—and use a shared hash function $h(x)$ for both tables. That way, any operation that probes both $\mathcal{H}_{\mathrm{full}}$ and $\mathcal{H}_{\mathrm{small}}$ still traverses a single contiguous region of memory around $h(x)$ (stretching the physical scan cost of $\mathcal{H}_{\mathrm{small}}$ by a factor of $\Theta(\varepsilon^{-1})$).

Insertions go directly into $\mathcal{H}_{\mathrm{small}}$, and a query simply searches both tables. After every $\Theta(\varepsilon m)$ words of insertions, we perform a global rebuild that merges $\mathcal{H}_{\mathrm{small}}$ into $\mathcal{H}_{\mathrm{full}}$ using $O(1)$ sequential passes over the table. Because the rebuild occurs only once every $\Theta(\varepsilon m)$ words of updates, its $O(m)$ cost amortizes to $O(\varepsilon^{-1})$ per inserted word—or $O(|x|/\varepsilon)$ for an item $x$. To support deletions without making negative queries depend on the key length, we keep constant-size fingerprints of deleted static keys in another interleaved table, checking for collisions during rebuilding. The details, together with the low-load deletion mechanism, appear in § 9 and Appendix § 14. Putting these pieces together gives our main result:

As an immediate corollary we also get the following result in the external memory model, establishing the existence of a linear-probing-like data structure for items of arbitrary sizes.