Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!mintaka!spdcc!iecc!compilers-sender
From: rfg@ncd.com (Ron Guilmette)
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design
Message-ID: <2980@lupine.NCD.COM>
Date: 13 Dec 90 06:40:27 GMT
References: <9012111512.AA14873@iecc.cambridge.ma.us> <1990Dec12.221425.569@zoo.toronto.edu>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: rfg@ncd.com (Ron Guilmette)
Organization: Network Computing Devices, Inc., Mt. View, CA
Lines: 40
Approved: compilers@iecc.cambridge.ma.us

In article <1990Dec12.221425.569@zoo.toronto.edu> henry@zoo.toronto.edu (Henry Spencer) writes:
>
>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's point is well taken, however there are *some* places where I think
that it is probably worth the effort to try to find a *perfect* hash
function.  Keyword tables in compilers and opcode tables in assemblers
come to mind.

So perfect hash functions may be useful somtimes.

Note however that *minimal* perfect hash functions are not only never
absolutely *required*, but (as Doug Schmidt pointed out to me) they may
actually be *inefficient*!!!

The reason is that in a not-quite-minimal (but still perfect) hash
function, you will never have any "collisions" (so you don't have to waste
time on dealing with such cases) and also, if you happen to look up an
input key which does not even have a corresponding entry in your hash
table, then you will hash that input key into a hash key whose
corresponding primary table entry is empty!  In such cases, you actually
SAVE TIME (relative to the case where you have a *minimal* perfect hash
function) because you won't even have to do a single comparison (of any
pair of complete keys).

[In a later message, Ron also points out:]

See also "The Art of Computer Programming" by Donald Knuth, book 3,
section 6.4.

-- 

// Ron Guilmette  -  C++ Entomologist
// Internet: rfg@ncd.com      uucp: ...uunet!lupine!rfg
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.