Elaine M. McGraw (née Boehme) was an American computer programmer who, together with Arthur Samuel and Gene Amdahl, invented open addressing based hash tables in 1954.

After studying economics, McGraw began working as a computer programmer for The Prudential Life Insurance Company in the early 1950s, using a UNIVAC computer. Prudential sent her to IBM to learn how to program the IBM 701, but (believing that Prudential would not purchase this computer) she applied for a job at IBM, and was hired there in 1953 by Gene Amdahl. She continued to work at IBM until at least 1970.[1]

In 1954, McGraw was working with Amdahl and Arthur Samuel on an assembler (a program for converting a textual description of a sequence of computer instructions into machine code) and she was tasked with implementing a symbol table for it.[1] Together, Amdahl, McGraw, and Samuel solved this problem by inventing the methods of open addressing and linear probing, still frequently used in modern hash table data structures.[2][3] This was not the first use of hash tables – hash tables with chaining had already been described in a 1953 memo by Hans Peter Luhn[4] – but was nevertheless an influential early contribution to the theory of data structures.

References

  1. ^ a b Konheim, Alan G. (2010), Hashing in Computer Science: Fifty Years of Slicing and Dicing, John Wiley & Sons, p. 180, ISBN 9781118031834.
  2. ^ Peterson, W. W. (April 1957), "Addressing for random-access storage", IBM Journal of Research and Development, Riverton, NJ, USA: IBM Corp., 1 (2): 130–146, doi:10.1147/rd.12.0130.
  3. ^ Knuth, Donald (1963), Notes on "Open" Addressing, archived from the original on 2016-03-03, retrieved 2016-01-17
  4. ^ Mehta, Dinesh P.; Sahni, Sartaj (28 October 2004), Handbook of Datastructures and Applications, pp. 9–15, ISBN 1-58488-435-5


Categories