CHAPTER 8
Hash Functions
8.1 THE ORIGIN OF HASHING
The history of the hashing concept is described in both [Knuth 1973], the third volume of Knuth’s seminal work, The Art of Computer Programming, and in the paper “Hashing” by D. G. Knott [Knott 1975].
The website http://www-03.ibm.com/ibm/history/ provides access to various documents relating to IBM’s role in the development of computers. The following material in derived in part from the transcription of a December 10, 1970 Oral History of IBM Technology1 interview of Elaine M. McGraw (née Boehme).
Nat Rochester was the software project manager for the IBM 701 machine; together with Gene M. Amdahl, Elaine M. McGraw (née Boehme), and Arthur L. Samuel, he considered a key-value-to-address machine for the 701 assembler.
Samuel claims (in a private communication to Knott cited in [Knott 1975]) that when confronted with the problem of collisions, Amdahl invented linear open addressing (see Chapter 13).
8.1.1 Biographical Notes
- Nat Rochester studied electrical engineering at the Massachusetts Institute of Technology (MIT) and was working in acoustics at the outset of World War II. During the war, he worked on radar at the MIT Radiation Laboratory and at Sylvania building equipment for the radiation laboratory. After the war, he worked on the arithmetic unit for Whirlwind and on cryptanalysis equipment for the National Security Agency (NSA). Deciding in 1948 that computers would be a “major thing,” Rochester joined IBM where he urged ...
