For nearly six decades, the central open question in the study of hash tables has been to
determine the optimal achievable tradeoff curve between time and space. State-of-the-art …

A dictionary data structure maintains a set of at most n keys from the universe U under key
insertions and deletions, such that given a query x∈U, it returns if x is in the set. Some …

Dictionaries have been one of the central questions in data structures. A dictionary data
structure maintains a set of key-value pairs under insertions and deletions such that given a …

Modern work on hashing has led to hash tables with extraordinary guarantees. However,
these data structures are too complex to be taught in (even an advanced) data structures …

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work
“succincter” by Pǎtraşcu 1 showed that any aB-tree can be stored using only two bits of …

A dynamic dictionary is a data structure that maintains sets of cardinality at most $ n $ from a
given universe and supports insertions, deletions, and membership queries. A filter …

We consider the problem of dynamically assigning n elements unique indices, known as
hashcodes, in the range [(1+ o (1)) n]. This problem is known as perfect hashing and is …

In this paper, we design a new succinct static dictionary with worst-case constant query time.
A dictionary data structure stores a set of key-value pairs with distinct keys in $[U] $ and …