Abstract Dictionaries Using Variable-Length Keys and Data, with Applications ∗

We consider the problem of maintaining a dynamic dictionary in which both the keys and the associated data are variable-length bit-strings. We present a dictionary structure based on hashing that supports constant time lookup and expected amortized constant time insertion and deletion. To store the key-data pairs (s1, t1)... (sn, tn), our dictionary structure uses O(m) bits where m = � (max(|si | − log n, 1) + |ti|) and |si | is the length of bit string si. We assume a word length w> log m. We present several applications, including representations for semi-dynamic graphs, ordered sets for integers in a bounded range, cardinal trees with varying cardinality, and simplicial meshes of k dimensions. These results either generalize or simplify previous results.