Early On
Bob Hopgood first got interested in Hash Tables in 1963 when he was one of a team designing a Fortran Compiler for the IBM 7030 (Stretch). Tables were used for everything from Lexical Analysis to Common Sub-expression recognition. Access had to be fast. Hash Tables were first used in 1953 but became well known when used in the IBM 701 assembler in 1954 by Samuel, Amdahl, and Boehm.
Hash Tables are derived from standard Table Look-Up. For standard Table Look-Up, the Average Length of Search (A) for N entries is A = 0.5 (N+ 1).
Split the table in two and put half the entries in each reduces A to 0.25 (N + 2).
Split into four and A becomes 0.125 (N + 4).
So if the table is of length M why not split the table into M?
A Linear Hash defines a function hash that divides the keys into M sets nearly equal in size. To enter or look-up an entry is:
- (1) i = hash(KEY)
- (2) If ith entry is empty or contains KEY, exit
- (3) Otherwise, i = i + 1 (modulo M)
It is Linear because i is incremented by 1 or some other constant value. For Linear Hash Tables, A = (2 - S) / (2 - 2S) where S = N / M. Amazingly, A is independent of the number of entries. It only depends on how full the table is. A is about 3 (approx) when the table is 80% full.
In 1965, Alex Bell and Bob Hopgood wrote a fast multi-dialect Lexical Analyser for the Atlas Algol Compiler. They pioneered the use of the Quadratic Hash method when the table size is a power of 2:
- (1) i = hash(KEY); inc = 1;
- (2) If ith entry is empty or contains KEY, exit
- (3) Otherwise, inc = inc + 1; i = i + inc (modulo M)
The Average Length of Search is improved significantly.
Computer Animation
In 1968, Bob Hopgood wrote a book on Compiling Techniques for a Course that was taught at Brunel University. The Atlas Computer Laboratory had an SC4020 microfilm recorder which could be used to produce computer animated films. He produced a set of six films to show the power of the Linear and Quadratic Hash methods. One had a soundtrack produced using a VCS3 synthesiser. Only recently has it been possible to redo these films using SVG.
- Hash Derivation
- Linear Hash: Random Keys
- Quadratic Hash: Random Keys
- Linear Hash: User Keys
- Quadratic Hash: User Keys
- Quadratic versus Linear
Bob Hopgood wrote the SVG animations and the sounds were done by Paul Hopgood.
Copies of the original films are available on the Chilton website: