3176	 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 and N - . The method requires 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. Gaussian elimination parsing searching sparse matrix table compression table lookup
