Storing a Sparse Table The problem of storing and searching large sparse tables is ubiquitous in computer science. The standard technique for storing such tables is hashing, but hashing has poor worst-case performance. We propose a good worst-case method for storing a static table of n entries, each an integer between 0 and N - 1. The method requires 0(n) w words of storage and allows O(logn N) access time. Although our method is a little complicated to use in practice, our analysis shows why a simpler algorithm used for compressing LR parsing tables works so well. CACM November, 1979 Tarjan, R. Yao, A. Gaussian elimination, parsing, searching, sparse matrix, table compression, table lookup 3.74 4.12 4.34 5.25 CA791104 DB January 23, 1980 11:24 AM 3041 4 3176 3126 4 3176 3176 4 3176 2905 5 3176 3176 5 3176 3176 5 3176 3176 5 3176