Hash Functions and Their Applications       


 Nick M. Mitchell photo photo

Hash Functions and Their Applications - overview

IBM has a long history of making fundamental contribution to Hash Functions and their applications. Carter and Wegman discovered the use of Universal Classes of Hash Functions which have the property that when used for Hash Tables there are no inputs which are bad for too many of the functions within the class. Thus this was one of the first important worse case random algorithms. This class can also give a secure one time pad like authentication code.

Fagin, Nievergelt, Pippenger, and Strong showed how to build an extendible hash table with implications for associative stores on disks. The hash table dynamically and gracefully grows and shrinks as the database grows and shrinks.

Rigoutsos and Califano showed how to use hashing to do fuzzy matching. Halevi and Krawczyk have constructed very fast almost Universal Classes for use in cryptography. (All of these are important papers. Some are actually a few papers.) Sevitsky is currently looking for practical very efficient hash tables.

This page should point to Algorithms and Theory as a parent. Perhaps it might also point to IM as well but I'm not sure.