William Kuszmaul

The Power of Two-Choice Linear Probing

Amir Azarmehr, Michael A. Bender, William Kuszmaul +1

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…

Lower Bounds for Linear Hashing via Arithmetic Kakeya

Ainesh Bakshi, Alex Conway, Hanna Komlós +2

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 $Z_{p}$ and…

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

Yang Hu, William Kuszmaul, Jingxun Liang +3

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 conjectur…

Tight Bounds for Memory Allocation With and Without Request Fragmentation

Michael A. Bender, Alex Conway, Martín Farach-Colton +3

The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known…

Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries

Guy E. Blelloch, Yang Hu, William Kuszmaul +2

The dynamic dictionary is a fundamental data structure that maintains a set $S \subset [U]$ of size $n$ (we assume $n = U^{1 - Θ (1)}$ ), supporting insertions, deletions and membership q…

Dynamic Entropy-Encoded Arrays in O(1) Time with Nearly Optimal Space

Guy E. Blelloch, Yang Hu, William Kuszmaul +2

We show how to implement a dynamic array $A [1, n]$ with symbols from a fixed alphabet $Σ$ , while supporting $O (1)$ -time queries and updates, and using a total space of $$ \log \bin…

An Analysis of Brent's Insertion Method for Hash Tables

William Kuszmaul

In 1968, Richard P.~Brent introduced a new way of building a hash table that, at least empirically, achieves a remarkable property: Even if the hash table is filled to 100\% full,…

Succinct and Fast Tiny Pointer Hash Tables

Xilin Tang, Yuqi Mai, William Kuszmaul +1

Hash tables sit on the critical path of many systems, yet modern designs still force a trade-off between fast operations and high memory overhead. We revisit this trade-off and pre…

Fast Insertion for Bucketized Cuckoo Hashing

Tolson Bell, William Kuszmaul

Bucketized cuckoo hashing is a practically efficient hash table scheme in which each object $u$ is stored in one of two buckets $h_{1} (u), h_{2} (u)$ of capacity $ℓ$ . For any bucket…

Linear Probing with Non-Greedy Insertions

Andrew Krapivin, William Kuszmaul, Yixuan Wang +1

Linear probing hash tables classically use a \emph{greedy} insertion strategy, placing a key $u$ in the first available position out of $h (u), h (u) + 1, h (u) + 2, \dots$ . If the h…

Quadratic Probing Revisited: Smoothed Analysis and the Fall of Robin Hood

Yang Hu, William Kuszmaul, Jingxun Liang +3

Quadratic probing is one of the most widely used open-addressing hash-table schemes in practice, but after more than half a century, even its most basic performance guarantees rema…

History-Independent Load Balancing

Michael A. Bender, William Kuszmaul, Elaine Shi +1

We give a (strongly) history-independent two-choice balls-and-bins algorithm on $n$ bins that supports both insertions and deletions on a set of up to $m$ balls, while guaranteeing…

Succinct Dynamic Rank/Select: Bypassing the Tree-Structure Bottleneck

William Kuszmaul, Jingxun Liang, Renfei Zhou

We show how to construct a dynamic ordered dictionary, supporting insert/delete/rank/select on a set of $n$ elements from a universe of size $U$ , that achieves the optimal amortize…

Static Retrieval Revisited: To Optimality and Beyond

Yang Hu, William Kuszmaul, Jingxun Liang +3

In the static retrieval problem, a data structure must answer retrieval queries mapping a set of $n$ keys in a universe $[U]$ to $v$ -bit values. Information-theoretically, retrieva…

Fingerprint Filters Are Optimal

William Kuszmaul, Jingxun Liang, Renfei Zhou

Dynamic filters are data structures supporting approximate membership queries to a dynamic set $S$ of $n$ keys, allowing a small false-positive error rate $ε$ , under inse…

cs.DS2025★ 2 cited

Optimal Non-Oblivious Open Addressing

Michael A. Bender, William Kuszmaul, Renfei Zhou

A hash table is said to be open-addressed (or non-obliviously open-addressed) if it stores elements (and free slots) in an array with no additional metadata. Intuitively, open-addr…

Optimal Bounds for Open Addressing Without Reordering

Martin Farach-Colton, Andrew Krapivin, William Kuszmaul

In this paper, we revisit one of the simplest problems in data structures: the task of inserting elements into an open-addressed hash table so that elements can later be retrieved…

Tight Analyses of Ordered and Unordered Linear Probing

Mark Braverman, William Kuszmaul

Linear-probing hash tables have been classically believed to support insertions in time $Θ (x^{2})$ , where $1 - 1/ x$ is the load factor of the hash table. Recent work by Bender, Kuszm…

Efficient $d$ -ary Cuckoo Hashing at High Load Factors by Bubbling Up

William Kuszmaul, Michael Mitzenmacher

A $d$ -ary cuckoo hash table is an open-addressed hash table that stores each key $x$ in one of $d$ random positions $h_{1} (x), h_{2} (x), \dots, h_{d} (x)$ . In the offline setting, where…

Tight Bounds and Phase Transitions for Incremental and Dynamic Retrieval

William Kuszmaul, Aaron Putterman, Tingqiang Xu +2

Retrieval data structures are data structures that answer key-value queries without paying the space overhead of explicitly storing keys. The problem can be formulated in four sett…

Tight Bounds for Classical Open Addressing

Michael A. Bender, William Kuszmaul, Renfei Zhou

We introduce a classical open-addressed hash table, called rainbow hashing, that supports a load factor of up to $1 - ε$ , while also supporting $O (1)$ expected-time queri…

A Nearly Quadratic Improvement for Memory Reallocation

Martin Farach-Colton, William Kuszmaul, Nathan Sheffield +1

In the Memory Reallocation Problem a set of items of various sizes must be dynamically assigned to non-overlapping contiguous chunks of memory. It is guaranteed that the sum of the…

Scheduling Jobs with Work-Inefficient Parallel Solutions

William Kuszmaul, Alek Westover

This paper introduces the \emph{serial-parallel decision problem}. Consider an online scheduler that receives a series of tasks, where each task has both a parallel and a serial im…