Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sdd.hp.com!think.com!paperboy!hsdndev!spdcc!iecc!compilers-sender
From: johnl@iecc.cambridge.ma.us (John R. Levine)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design, bibliography
Message-ID: <9012111512.AA14873@iecc.cambridge.ma.us>
Date: 11 Dec 90 20:12:51 GMT
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: johnl@iecc.cambridge.ma.us (John R. Levine)
Organization: I.E.C.C.
Lines: 30
Approved: compilers@iecc.cambridge.ma.us
In-Reply-To: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca>

In article <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> you write:
>How does one build a hash function with minimal table size and minimal
>collisions for a known set of hash strings?

The problem of designing a hash algorithm that maps N identifiers into
unique slots in an N entry table is known as perfect hashing.  It has been
studied sporadically over the years.  There are algorithms known, but they
are all very slow.  Here are some references:

R. J. Cichelli, "Minimal perfect hash functions made simple," CACM 23:1,
Jan 1980, pp 17-19.

G. Jaeschke et al., comment on article above, CACM 23:12, Dec 1980, pp.
728-729.

G. Jaeschke, "Reciprocal hashing: a method for generating minimal perfect
hash functions," CACM 24:12, Dec 1981, pp. 829-833.

R. Sprugnoli, "Perfect hashing functions: a single probe retrieving method
for static sets," CACM 20:11, Nov 1977, pp. 841-850.

A brief visit to my 40 shelf-feet of computer journals didn't turn up
anything more recent except for some data base applications.  If someone
has a breakthrough in perfect hashing to report, I'd love to hear about it.
-- 
Regards,
John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.