Report Number: CS-TR-78-683
Institution: Stanford University, Department of Computer Science
Title: Storing a sparse table
Author: Tarjan, Robert Endre
Date: December 1978
Abstract: The problem of storing and searching large sparse tables arises in compiling and in other areas of computer science. The standard technique for storing such tables is hashing, but hashing has poor worst-case performance. We consider good worst-case methods for storing a table of n entries, each an integer between 0 and N-1. For dynamic tables, in which look-ups and table additions are intermixed, the use of a trie requires O(kn) storage and allows O($\log_k$(N/n)) worst-case access time, where k is an arbitrary parameter. For static tables, in which the entire table is constructed before any look-ups are made, we propose a method which requires O(n $log^{(\ell)}$ n) storage and allows O($\ell \log_n N$) access time, where $\ell$ is an arbitrary parameter. Choosing $\ell$ = $\log^* n$ gives a method with O(n) storage and O(($\log^* n$)($\log_n N$)) access time.
http://i.stanford.edu/pub/cstr/reports/cs/tr/78/683/CS-TR-78-683.pdf