CS Paper Radar

Fine-Grained Analysis of SIMD-Based Hash Table Implementations

Cyril Nicaud, Pablo Rotondo

cs.DS ·submitted 2026-10-01 19:08 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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.61
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

A Sharp Analysis of Fixed Offset Hash Tables

cs.DS ·2026-10-22 ·Yuhao Guo, Seth Pettie, Chengzhang Wan
similarity 0.59
Abstract

We consider the class of open addressing hash tables that uses a fixed offset sequence $r_0,r_1,\ldots,r_{n-1}$ to find an open slot in the table. As special cases this subsumes linear probing ($r_i=i$) and quadratic probing ($r_i=i^2$). We give a simple analysis that the expected insertion time when the load factor is $1-ε$ is $O(ε^{-2})$. This bound is tight for linear probing (but not for quadratic probing), so the analysis cannot be improved at this level of generality.

0.39

Catalan Hashing: Efficient Linear Probing for Variable-Length Items

cs.DS ·2026-11-03 ·Alex Conway, Hanna Komlós, William Kuszmaul
similarity 0.57
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

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

cs.CR cs.DSmath.COmath.PR ·2026-09-30 ·Maksym Petkus
similarity 0.57
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.

0.36

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

cs.DS ·2026-10-23 ·Andrew Krapivin, William Kuszmaul
top venue similarity 0.57
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

Geometric Hashing in MPC with Applications to Clustering and Stochastic Embeddings

cs.DS cs.CG ·2026-10-15 ·Sujoy Bhore, Arnold Filtser, Eunjin Oh, Hyeonjun Shin, Himanshi Singh
top venue similarity 0.57
Abstract · To appear in SODA'27

In this paper we study consistent hashing (a.k.a. sparse partitions) for doubling metrics in the Massively Parallel Computation (MPC) model. A $(Γ,Λ)$-hash with diameter bound $Δ$ partitions a metric space into clusters of diameter at most $Δ$ such that every ball of radius $Δ/Γ$ intersects at most $Λ$ clusters in expectation. Consistent hashing has emerged as a central tool in geometric MPC algorithms. However, so far it has been solely used in Euclidean spaces, where it can be pre-computed. On the other hand, in cases where the metric space is received as input and unknown in advance, no previous parallel construction was known. We present the first fully scalable MPC algorithm over machines with local space $n^σ$, that given an $n$-point metric space with doubling dimension $d\leq O(σ\log n)$, samples a randomized $(Γ,2^{O(d/Γ)})$-hash in $O(d/σ^3)$ rounds. There is a dichotomy: if the doubling dimension is $d=Ω(σ\cdot\log n)$, a polynomial number of rounds is required to compute such a hash. We conclude by showing that this MPC primitive yields $O(d/σ^3)$-round fully scalable MPC algorithms for a broad class of fundamental geometric problems in doubling metrics, including stochastic tree embeddings with $O(\log n)$ expected distortion, constant factor approximation for facility location, bicriteria $(O(ε^{-2}),1+ε)$-approximation for $k$-median and $k$-means.

0.73

Consensus for Compressed Static Functions

cs.DS ·2026-09-30 ·Dominik Rosch, Jonatan Ziegler
theory similarity 0.55
Abstract · 28 pages, 5 figures, with appendix

The Consensus technique marked a breakthrough in the construction of minimal perfect hash functions (MPHFs), reaching a linear tradeoff between construction time and space overhead relative to the optimum. Consensus provides a clever scheme to search for and encode seeds of tasks in random data structures. We apply Consensus to the related field of compressed static functions (CSFs). These data structures store a function $f: S \to Σ$ such that querying a key $x \in S$ returns $f(x)$ and querying $x \not \in S$ returns an arbitrary value. CSFs do not need to store the keys $S$ and only need space close to the zeroth-order empirical entropy of the multiset of values. Often, some values are much more common than others. In these cases, CSFs can use less space than their non-compressed counterparts. CSFs are a useful building block, for example in database design and bioinformatics. We introduce Consensus-CSF, which can reach arbitrarily close to the empirical entropy $n H_0$, with a construction time of $n \exp(\tilde{\cal{O}} (\sqrt{1 / δ}))$ for space usage of $n H_0 (1 + δ)$ when assuming some parameters of the value distribution to be constants. This tradeoff beats previously implemented approaches that can only reach some fixed threshold above the entropy lower bound. We enable Consensus in the setting of CSFs, which is less structured than MPHFs, with the introduction of task insertions. Our approach randomly distributes the keys into one-bit Consensus tasks and then strategically inserts additional tasks in places where the construction would get stuck otherwise. We provide an implemented version of our algorithm which reaches the same order of magnitude in space overhead as competitors but is not competitive in practice. Beyond these results, we present a new way to think and reason about Consensus, which may also be applied to other problems.

0.29

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.55
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