Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!ima!johnl
From: johnl@ima.UUCP
Newsgroups: mod.compilers
Subject: Re: Looking for minimal perfect hash functions.
Message-ID: <465@ima.UUCP>
Date: Wed, 28-Jan-87 13:52:26 EST
Article-I.D.: ima.465
Posted: Wed Jan 28 13:52:26 1987
Date-Received: Fri, 30-Jan-87 06:08:41 EST
References: <526@sargas.usc.edu>
Sender: johnl@ima.UUCP
Reply-To: pedz@bobkat.UUCP (Pedz Thing)
Organization: Digital Lynx, Inc; Dallas, TX
Lines: 23
Keywords: hashing reserved words
Approved: compilers@ima.UUCP

Original-sender:

I am curious to know if any really uses this technique (of minimal
perfect hashing).  The reason I ask is that it involves polynomials
which are rather time consuming to compute.  Or am I wrong about that?
I always use a binary search method since that comsumes less than 10
compares of strings.  Usually the compares fail on the first
character.  So in about 10 add's and divide by two (hopefully done
with a shift) followed by a compare, you are done.  That's pretty
quick.  Also, the keyword list can change easily without much rewrite
of the code.

What does the typical "real" polynomial come out to be?  Does it
really take less time than the binary search method.  (I would judge
this based upon a miss of the table since most identifiers in a
program are not keywords.)
-- 
Perry Smith
pedz@bobkat
{ti-csl,infotel}!pollux!bobkat!pedz
--
Send compilers articles to ima!compilers or, in a pinch, to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | cca}!ima
Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request