Adaptive Hashing (Is There Anything New In Hashing Under The Sun?)

Wednesday, October 3, 2007 - 3:42pm

SPEAKER: ALAN KONHEIM, Professor Emeritus of Computer Science, UCSB
DATE: Wednesday, October 10, 2007
TIME: 3:30 – 4:30 p.m.
PLACE: Computer Science Conference Room, Harold Frank Hall Room 1132


Gene Amdahl, Elaine Boehme and Arthur Samuel implemented a key value-to-address translation process, now called /hashing/, for the IBM 701 assembler at the IBM Poughkeepsie Lab in 1953. To resolve translation conflicts (/collisions/) – two keys translating to the same hashed-address – Amdhal invented /linear probing/. Another IBM employee, Wes Peterson published a simulation analysis in 1957 of the cost of linear probing.

Well over 100 papers were published during 1957-2007 on various aspects of hashing, protocols embellishing linear probing and their analysis. One might think that there is nothing new in hashing under the sun … perhaps … but the speaker will describe something /almost/ new.


After completing graduate study in 1960, Dr. Konheim became a Research Staff Member at the IBM Thomas J. Watson Research Center (Yorktown Heights, New York).
During his 22 years in the Department of Mathematical Sciences at IBM, he researched the applications of mathematics in computer science problems. Starting in the mid-1960’s, he became the Manager of the Mathematical Sciences’ cryptography program; in particular, the evaluation of the Data Encryption Standard (DES). In 1982, he accepted a position as a professor in the Computer Science Department at the University of California, Santa Barbara. In his 24 years at UCSB, he taught courses in Assembly Language, Performance Evaluation, Computer Networks and Cryptography. He developed CMPSC 178 (Introduction to Cryptography) and offered this course 21 times at UCSB and three times at the Technion (Haifa, Israel), LaTrobe University (Melbourne, Australia) and at the University of Hawaii, Honolulu. He retired from UCSB on July 1, 2005. He spent the summers at the National Security Agency (Fort George G. Meade, Maryland), the Communications Research Division at the Institute for Defense Analysis (Princeton, New Jersey) and the National Security Agency.