Dictionaries using variable-length keys and data, with applications
Daniel K. Blandford, Guy E. Blelloch · Symposium on Discrete Algorithms · 2005
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.