Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!decvax!yale-com!leichter
From: leichter@yale-com.UUCP (Jerry Leichter)
Newsgroups: net.lang
Subject: Re: hash function generator - (nf)
Message-ID: <2117@yale-com.UUCP>
Date: Tue, 4-Oct-83 09:34:11 EDT
Article-I.D.: yale-com.2117
Posted: Tue Oct  4 09:34:11 1983
Date-Received: Thu, 6-Oct-83 21:42:36 EDT
References: hp-pcd.1984
Lines: 20

There is work of two sorts done in this direction.  First, there are some
articles on generating PERFECT hash functions for given sets of inputs.
A perfect hash function has no collisions at all.  You would use something
like this to produce a very quick hash-table lookup for keywords in a compiler.
You can find these articles in the CACM within the last 5 years or so.

Second, there is a general approach, due to Carter and Wegman.  They
introduce "universal classes of hash functions".  Such a class has the
property that a randomly chosen member is highly likely to give a very good
hash ("highly likely" and "very good" having specific meanings in this context)
for ANY particular set of inputs to be hashed.  The only place I know of in
which this has been written up is in Proceedings of the 9th SIGACT (1977),
page 106.  They prove some practical classes of functions - essentially of
the form Ax+B mod C, where C is fixed for the class and A and B vary to give
all class members - are universal.

Beyond this, getting any sort of guarantees of the quality of a hash function
for a given, random set of inputs is extremely difficult.
							-- Jerry
					decvax!yale-comix!leichter leichter@yale