Konheim - Hashing in computer science: fifty years of slicing and dicing

PREFACE

0.1 WHAT IS HASHING

The Merriam-Webster Dictionary (1974) provides several definitions for hash :

• noun: an American food made by combining and compressing chopped-up leftoversmeat, eggs, and potatoes.
• verb: to chop into small pieces; make into hash; mince.
• noun: colloquial for hashish (or hashish ), the resin collected from the flowers of the cannabis plant. The primary active substance is THC (tetrahydrocannabinol), although several other cannabinoids are known to occur. Hash is usually smoked in pipes, water pipes, joints, and hookahs, sometimes mixed with cannabis flowers or tobacco. It can also be eaten.

A search for hashing on Google yields 1,720,000 hits; of course, it doesnt come close to the 670,000,000 hits for sex or even the 129,000,000 hits for money , but then

Although hashing may be exhilarating and even intoxicating, this book deals with its applications in computer science relating to the processing of information that is both old (1953+) and new (1990+).

0.2 MY HASHING ROOTS

Nat Rochester was the software project manager for the IBM 701 machine; together with Gene M. Amdahl, Elaine M. McGraw (ne Boehme), and Arthur L. Samuel, they considered a key-value-to-address machine for the 701 assembler. Several sources agree that Amdahl invented linear open addressing, a form of hashing ( aka scatter storage), when confronted with the problem of collisions.

I was a Research Staff member in the Department of Mathematical Sciences at the IBM Thomas J. Watson Research Center in Yorktown Heights (New York) from 1960 to 1982. Sometime in 1964, I was asked by my manager to meet with Wes Peterson (19242009) to learn about his work on hashing. Wes was a former employee of and now consultant to IBM; in 1964, he was a faculty member at one of the University of Florida campuses. Wes used simulation to evaluate the performance of linear probing , an algorithm developed during the design of the IBM 701 machine. As a result of our conversation, I started to work with Benjamin Weiss, then a post-doc at IBM, now a Professor Emeritus at the Hebrew University in Jerusalem, to develop a combinatorial analysis of hashing with linear probing.

In a footnote on page 529 of The Art of Computer Programming: Volume 3/Sorting and Searching (Addison-Wesley Publishing Company, 1973), Professor Donald Knuth wrote that his running-time analysis of Algorithm L was the first non-trivial algorithm I had ever analyzed satisfactorily. He also noted that more than ten years would go by before the derivation got into print! Algorithm L is central to the performance of linear probing , which is essentially the hashing algorithm proposed by Gene Amdahl. Ben Weiss and I found the formula Nj ( j + 1)( j 1) (Theorem 13.2 is Knuths Algorithm L), which counts the number of hash sequences inserting j keys in a hash table of size j + 1 leaving the last hash table address unoccupied. First, we computed by hand the values Nj for j = 2, 3, 4 until we recognized the form of the algebraic expression ( j + 1)( j 1), a technique that I have suggested to students in other contexts.

I contacted Wes again in 1997, where he was and remains today a Professor of Computer Science at the University of Hawaii. I inquired about a sabbatical leave there in 1999. My wife and I visited Wes and his wife Hiromi at their home in December 1997 while celebrating our 40th anniversary. Wes had just been awarded the Japan Prize, and both Petersons were both contemplating sabbatical leaves in Japan starting in January 1999. Timing is everything! I was hired by Wes and Hiromi to watch over their dog Koko; I was certainly the highest paid dog sitter in the Hawaiian Islands. Koko was a constant source of innocent merriment during my 5-month sabbatical; he curiously developed a significant taste for Hebrew National salami, and our acquiescing to his new found tastes was criticized by both Wes and Kokos veterinarian. However, before leaving for Japan, Wes warned my wife that Koko might die before their return. The miraculous and curative powers of Hebrew National salamiWe Answer To a Higher Authority added 2 years to Kokos life. We saw Wes again when we returned to Hawaii to celebrate our 50th anniversary in July 2007.

0.3 THE ORIGINAL APPLICATION OF HASHING (DATA STORAGE)

When data are stored and manipulated in a computer system, a mechanism must be provided to access the data easily. We view information in storage as composed of records of variable sizes located in the system storage media in a variety of regions, especially in dynamic file systems. A unique key is associated with and stored in each record. This key could be a name or a suitable number, but in general, any string can serve as a unique identifier. The key is used by the programs processing the data to locateto SEARCH for the address ofthe desired record. When a telephone directory is used to determine a telephone number, SEARCH is somewhat easier than the general instance of file management because the records composed of the triple (Name Address TelephoneNumber) are stored sorted on the Name field .