(lat. On Dynamic Dictionaries Using Little Space) ⋆

Abstract. We develop dynamic dictionaries on the word RAM that use asymptotically optimal space, up to constant factors, subject to insertions and deletions, and subject to supporting perfect-hashing queries and/or membership queries, each operation in constant time with high probability. When supporting only membership queries, we attain the optimal space bound of Θ(n lg u) bits, where n and u are the sizes of n the dictionary and the universe, respectively. Previous dictionaries either did not achieve this space bound or had time bounds that were only expected and amortized. When supporting perfect-hashing queries, the optimal space bound depends on the range {1, 2,..., n + t} of hashcodes allowed as output. We prove that the optimal space bound is Θ(n lg lg u n +n lg) bits when supporting only perfect-hashing queries, n t+1 and it is Θ(n lg u n + n lg) bits when also supporting membership n t+1) lower bound. queries. All upper bounds are new, as is the Ω(n lg n t+1