Dynamic Dictionary with Subconstant Wasted Bits per Key
Tianxiao Li, Jingxun Liang, Huacheng Yu, Renfei Zhou · Society for Industrial and Applied Mathematics eBooks · 2024
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 [4] 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 [16].