Joe Celko's Thinking in Sets: Auxiliary, Temporal, and Virtual Tables in SQL

3.3. Hashing

The basic idea of hashing is that given input values, the hashing function will return a physical storage address. Writing hashing functions is not easy. If you are very lucky, the function can do this directly with your hardware, but it is more likely to return an address inside a hash table. The hash table is an array of physical addresses that fit into main storage which indexed by the hash function, so that “HashBucket [hash(key)] = physical location”.

There are many kinds of hashing functions, and you can start with a review of them in V. Y. Lum, P. S. T. Yuen, and M. Dodd, “Key-to-Address Transformation Techniques: A Fundamental Performance Study,” Communications of the ACM, April 1971, pp. 228-239.

3.3.1. Digit Selection ...