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 ( s 1 , t 1 ) ... ( s n , t n ), our dictionary structure uses O(m) bits where m = ?(max(| s i | -- log n , 1) + | t i | and | s i | is the length of bit string s i . 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.
dictionaries data applications dynamic association strings structure hashing timing log graph trees mesh general variability