William Kuszmaul

collaborators

15 papers

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

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

cs.DS2026

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…

cs.DS2026

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…

cs.DS2026

Linear Probing with Non-Greedy Insertions

Andrew Krapivin, William Kuszmaul, Jolyne Wang

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…