CS Paper Radar

MultiTable: A Faster Hash Table at any Physical Load Factor up to and Including One

Maksym Petkus

cs.CR cs.DSmath.COmath.PR ·submitted 2026-09-30 08:05 UTC · v1

Abstract

We present \emph{multitable} and its Rust reference implementation: a stable hash table both materially faster at equal physical memory and more flexible than the SwissTable in its Rust's hashbrown implementation. As an arithmetic mean over 84 configurations it delivers $\mathbf{2.1\times}$ hashbrown's throughput when both hash the same raw bytes and $\mathbf{1.9\times}$ when hashbrown is keyed on native integers, its best case; on negative lookups alone, $3.2\times$ and $2.9\times$. Multitable reaches \textbf{any physical load factor} up to and \textbf{including one} ($0.9999$ demonstrated), exactly for the requested capacity, compared to hashbrown which doubles at $0.777$ for 4-byte keys and values. At $75\%$ saturation of hashbrown (assumed average case of its rigid ladder) and multitable sized to $0.97$ physical load factor, hashbrown takes $66\%$ more space. The lookup probe count has no cliff as the load factor approaches one. Bucket size, physical load factor, and failure budget are parameters, and the multitable can be grown without rehashing. We implement two variants of multitable: plain and filtered. At equal physical memory on an Apple M2 Pro the filtered multitable leads hashbrown in all $84$ insert, hit, and miss configurations. Multitable is more \textbf{memory-efficient}, at equal mixed-lookup throughput on the map of $4$-byte keys and values the filtered multitable needs up to $12\%$ fewer bytes than hashbrown, and the plain multitable is $18\%$ smaller, holding $\mathbf{22\%}$ more keys in the same memory.

Closest papers

Nearest neighbours by meaning across the whole index.

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

cs.DS ·2026-11-03 ·Alex Conway, Hanna Komlós, William Kuszmaul
similarity 0.61
Abstract

A defining feature of the linear-probing hash table is its spatial locality: at load factor $1 - \varepsilon$, the hash table can be implemented so that each operation scans a single contiguous region of expected size $O(1/\varepsilon)$ (this is known as the \emph{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| \ge 1$. The main result of the paper is a new hash table called \emph{Catalan hashing}, which supports amortized expected scan cost $O(|x|/\varepsilon)$ for positive queries, $O(1/\varepsilon)$ for negative queries, and $O(|x|\varepsilon^{-1}\log^{1+δ}|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.

0.21

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

cs.DS ·2026-10-23 ·Andrew Krapivin, William Kuszmaul
top venue similarity 0.61
Abstract · 60 pages, 1 figure, to appear in SODA 2027

In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log \varepsilon^{-1})$, with high probability. This result represents an exponential improvement on insertion/deletion time over previous constructions, and disproves a conjecture of Bender, Kuszmaul, and Zhou that the product of worst-case query time and expected insertion/deletion time must be $Ω(\varepsilon^{-1})$.

0.35

Linear Hashing is Not That Awesome

cs.DS ·2026-08-24 ·Or Zamir
theory similarity 0.61
Abstract

Consider the canonical universal hash family $h(x)= ((ax+b)\text{ mod } p)\text{ mod } m$, where $a,b$ are chosen uniformly from $\mathbb Z_p$, which we call linear hashing, being used to hash $n$ elements into $m=Θ(n)$ buckets. For any universal family, the expected size of the largest bucket is at least $Ω(\log n / \log\log n)$ and at most $O(\sqrt{n})$. The only improvement upon these trivial bounds for linear hashing is a 2019 upper bound of $\tilde{O}(n^{1/3})$ by Knudsen. We show that for any $p$ sufficiently larger than $n$, there is a set of $n$ keys whose expected maximum load is $n^{Ω(1/\log\log n)}$, proving linear hashing does not have a polylogarithmic maximum load. We extend the same bounds to the classical multiply-shift hash family of Dietzfelbinger, Hagerup, Katajainen, and Penttonen. Our main contribution is an equivalence between the maximum load problem to a density variant of arithmetic Kakeya sets. We then complete the lower bound using a construction of Green and Ruzsa of a small set containing long arithmetic progressions with every difference in a prescribed range. Surprisingly, our equivalence also implies that any substantial improvement over Knudsen's upper bound would imply new results about standard arithmetic Kakeya sets. More precisely, an $O(n^{1/3-\varepsilon})$ upper bound would improve known bounds for unions of complete integer arithmetic progressions, while an $n^{o(1)}$ upper bound would imply Bourgain's arithmetic-progression criterion.

0.53

The Power of Two-Choice Linear Probing

cs.DS ·2026-09-30 ·Amir Azarmehr, Michael A. Bender, William Kuszmaul, Rose Silver
top venuetheory similarity 0.60
Abstract

This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected insertion and query time, as a function of the load factor $1 - ε$? We prove that the \emph{greedy two-choice insertion strategy} achieves polynomially better bounds than the single choice algorithm, but that one can even do \emph{much better} by using more sophisticated non-greedy strategies. Specifically, we show that there is an insertion strategy that does not evict elements (once an element is inserted, its hash choice is fixed) and that achieves expected query time $O(\log ε^{-1})$ with expected insertion time $O(ε^{-1})$. We then further show that, if one is allowed to evict elements (i.e., to change over time which hash function a given element uses), then it is possible to achieve expected query time $O(1)$ with expected insertion time $O(ε^{-1/2})$. This final result achieves an expected query time of $O(1)$ even when the hash table is filled to $100\%$ full. Combined, the results reveal that there is a surprisingly strong ``power of two choices'' phenomenon for linear-probing hash tables, allowing for a two-choice hash table to achieve significantly better bounds than what might at first seem to be possible.

0.39

Lower Bounds for Linear Hashing via Arithmetic Kakeya

cs.DS ·2026-08-25 ·Ainesh Bakshi, Alex Conway, Hanna Komlós, William Kuszmaul, Alek Westover
theory similarity 0.59
Abstract · updated to note concurrent work

Affine modular linear hashing is one of the simplest classical hash families. For a prime $p > u$, the hash function is obtained by choosing $s,t$ uniformly from $\mathbb{Z}_p$ and mapping each key $x \in \{0,\ldots,u-1\}$ to one of $n$ bins by $h(x) = [(sx+t) \bmod p] \bmod n$. Despite its simplicity, the maximum load of linear hashing remains poorly understood. For $n$ keys hashed into $n$ bins, the best known upper bound is $O((n \log n)^{1/3})$, whereas the best known lower bound is only $Ω(\log n / \log\log n)$. We prove a lower bound of $\exp(Ω(\log n / \log\log n))$ for universes of size $n^{1+o(1)}$. Surprisingly, there is a key set for which this load holds not just in expectation, but for every random seed. The proof is driven by two simple reductions: one transfers lower bounds from a real version of linear hashing to modular linear hashing, and the other transfers arithmetic Kakeya constructions to real hashing. We further show that, for sufficiently large $p$, the expected maximum loads in the modular and real settings are essentially the same, giving an alternative route to an $n^{1/3+o(1)}$ upper bound. Finally, we show that any uniform subpolynomial upper bound for either setting would imply a polynomial-length arithmetic Kakeya conjecture and hence the Kakeya conjecture for upper Minkowski dimension.

0.38

Fine-Grained Analysis of SIMD-Based Hash Table Implementations

cs.DS ·2026-10-01 ·Cyril Nicaud, Pablo Rotondo
similarity 0.57
Abstract

In recent years, several variants of classical hash table schemes have been developed by engineers in order to take advantage of the processor's internal parallelism using SIMD instructions, which make it possible to operate on multiple bytes simultaneously. At a small additional memory cost, this enables a significant speedup, making it a data structure that is increasingly popular in practice, when very high performance is required. In this article, we provide a detailed theoretical analysis of the dynamics of such hash tables. From a methodological standpoint, we use and adapt a technique developed by Wormald in the 1990s to study dynamic graphs. This approach, which can be adapted to many variants, enables us to accurately estimate the quantities of interest by capturing the dynamics of the data structure through systems of differential equations. Although complex, we provide an explicit description of the solutions of these systems, which can furthermore be efficiently approximated numerically. Our main results are stated with high probability, which is significantly more precise than average-case analyses, and they match experimental results remarkably well, even for hash tables of moderate size.

0.30

Quadratic Probing Insertions Are $ε^{-(1+o(1))}$ Time

cs.DS ·2026-08-28 ·Yang Hu, William Kuszmaul, Jingxun Liang, Stefan Walzer, Huacheng Yu +1 more
theory similarity 0.57
Abstract · 17 pages

First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - ε$, the hash table achieves $O(ε^{-1})$ expected insertion time. But even proving a bound of the form $f(ε^{-1})$ for any function $f$ has remained open. In this paper, we prove that the expected insertion time is $ε^{-(1 + o(1))}$. This settles the complexity of the data structure up to sub-polynomial factors in $ε^{-1}$.

0.18

Fresh-Priority Eviction for Cuckoo Filters: Exploiting Latent Randomness Under XOR Hashing

cs.DS ·2026-11-01 ·Min Liu
theory similarity 0.55
Abstract

Cuckoo filters are a widely adopted approximate membership query (AMQ) data structure that supports insertions, lookups, and deletions with low memory overhead. At high load factors, however, insertion performance degrades sharply due to the random-walk eviction process, which may require a large number of element relocations. Recent work on bucketized cuckoo hash tables has shown that \emph{fresh-priority eviction}, which preferentially evicts elements whose alternate bucket location has not yet been used, achieves $O(\ell m)$ total expected evictions for bucket size~$\ell$, an improvement over the standard random walk. In this paper, we show that this technique transfers to \emph{cuckoo filters} despite their use of XOR-based partial-key hashing. The key insight is that a fresh element's fingerprint, although stored in the table, is not examined by the eviction policy, so when the fingerprint length satisfies $k = Ω(\log m)$, the alternate bucket hash remains a near-uniform random variable, a property we call \emph{latent randomness}. We prove that under this condition the corruption graph remains subcritical and the total number of evictions is $O(\ell m \log m)$; we conjecture the tighter $O(\ell m)$ bound holds via the full amortized analysis of Bell and Kuszmaul. We further propose encoding the fresh/kicked state implicitly by the element's position within its bucket, requiring no additional per-element metadata. Experimental results on a filter with $2^{22}$ slots and $8$-bit fingerprints demonstrate $1.2\times$ to $2.4\times$ fewer evictions at load factors between $94\%$ and $99\%$ for bucket size $\ell = 8$, and a $1.73\times$ reduction in cumulative evictions to full capacity.

0.10