Optimal Static Dictionary with Worst-Case Constant Query Time

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 values in [σ], such that given a query x ∈ [ U ], it quickly returns if x is one of the input keys, and if so, also returns its associated value. The textbook solution to dictionaries is hash tables. On the other hand, the (information-theoretical) optimal space to encode such a set of key-value pairs is only OPT := log( U n ) + n logσ. We construct a dictionary that uses OPT + n ε bits of space, and answers queries in constant time in worst case . Previously, constant-time dictionaries are only known with OPT + n / poly log n space, or with OPT + n ε space but expected constant query time. We emphasize that most of the extra n ε bits are used to store a lookup table that does not depend on the input, and random bits for hash functions. The “main” data structure only occupies OPT + poly log n bits.

Authors

• Yang Hu
• Jingxun Liang
• Huacheng Yu
• Junkai Zhang
• Renfei Zhou

Keywords

• Data Structures
• Dictionaries
• Succinct Data Structures