Storing a sparse table
Robert Endre Tarjan, Andrew Chi-Chih Yao · Communications of the ACM · 1979
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 O ( n ) words of storage and allows O (log n 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.