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 [Pǎt08], or with OPT + n ε space but expected constant query time [Yu20]. 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.