Re: Looking for minimal perfect hash functions.

Pedz Thing <ihnp4!bobkat!pedz>
Wed, 28 Jan 87 12:52:26 cst

          From comp.compilers

Related articles
Looking for minimal perfect hash functions. tli@sargas.usc.edu (1987-01-25)
Re: Looking for minimal perfect hash functions. ihnp4!bobkat!pedz (Pedz Thing) (1987-01-28)
| List of all articles for this month |

Date: Wed, 28 Jan 87 12:52:26 cst
From: Pedz Thing <ihnp4!bobkat!pedz>
Summary:
Expires:
References: <526@sargas.usc.edu>
Original-sender:
Followup-To:
Distribution:
Organization: Digital Lynx, Inc; Dallas, TX
Keywords: hashing reserved words

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


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.