Dynamic Dictionary with Subconstant Wasted Bits per Key

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 query key, the data structure efficiently returns its value. The state-of-the-art dictionaries [BFK + 22] store n key-value pairs with only O(n log (k) n) bits of redundancy, and support all operations in O(k) time, for k ≤ log * n. It was recently shown to be optimal [LLYZ23b].

In this paper, we study the regime where the number of redundant bits is R = o(n), and show that when R is at least n/poly log n, all operations can be supported in O(log * n + log(n/R)) time, matching the lower bound in this regime [LLYZ23b]. We present two data structures based on which range R is in. The data structure for R < n/ log 0.1 n utilizes a generalization of adapters studied in [BKP + 22,LLYZ23a]. The data structure for R ≥ n/ log 0.1 n is based on recursively hashing into buckets with logarithmic sizes.