Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sdd.hp.com!think.com!mintaka!spdcc!iecc!compilers-sender
From: henry@zoo.toronto.edu (Henry Spencer)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design
Message-ID: <1990Dec12.221425.569@zoo.toronto.edu>
Date: 12 Dec 90 22:14:25 GMT
References: <9012111512.AA14873@iecc.cambridge.ma.us>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: henry@zoo.toronto.edu (Henry Spencer)
Organization: U of Toronto Zoology
Lines: 21
Approved: compilers@iecc.cambridge.ma.us

>>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...

Note that he didn't ask for zero waste space or zero collisions, just for
minimal both. Interpreting "minimal" not too strictly, this doesn't require
perfect hashing.  I don't have any specific algorithms to suggest for
imperfect hashing, however -- it's never seemed difficult to get a table
with only one or two collisions and not much extra space.

Actually, I have never figured out why people seem so obsessed with perfect
hashing, since the hash functions typically seem noticeably expensive, and
it has always seemed to me that a fast hashing function plus fast resolution
of occasional collisions would be easier and just as good.
-- 
Henry Spencer at U of Toronto Zoology, henry@zoo.toronto.edu   utzoo!henry
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.