4 citations · 8 across the 31 of their papers we have counts for
13 papers · 1 filter
Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing
Andrew Krapivin, William Kuszmaul
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to (for some parameter ), wh…
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 , the hash function is obtained by choosing uniformly from and…
Quadratic Probing Insertions Are 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 of size (we assume ), 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 with symbols from a fixed alphabet , while supporting -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 is stored in one of two buckets 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 in the first available position out of . 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 bins that supports both insertions and deletions on a set of up to balls, while guaranteeing…