Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site watdaisy.UUCP
Path: utzoo!watmath!watdaisy!gvcormack
From: gvcormack@watdaisy.UUCP (Gordon V. Cormack)
Newsgroups: net.lang.pascal
Subject: Re: Minimal Perfect Hashing Functions
Message-ID: <6772@watdaisy.UUCP>
Date: Tue, 27-Nov-84 22:26:14 EST
Article-I.D.: watdaisy.6772
Posted: Tue Nov 27 22:26:14 1984
Date-Received: Wed, 28-Nov-84 04:28:31 EST
References: <684@loral.UUCP>
Organization: U of Waterloo, Ontario
Lines: 33

You may (or may not) be interested in a paper by myself titled
"Practical perfect hashing" to appear the the next issue of
"The Computer Journal".

I am not claiming that this method is the best for a compiler, as
it requires 3 divisions per access.  Indeed, it is not clear to me
why there exists this great desire for a perfect hash function in
this case.  One can construct an ordinary hash table that performs
extremely well.  I also see little need for a minimal function,
as the number of keywords is quite small.

If anyone can't wait for the above article to appear, send me a 
message and I will send you a pre-print.

                          ABSTRACT

          A  practical method is presented that permits
     retrieval  from  a  table  in  constant time.  The
     method  is suitable for large tables and consumes,
     in  practice, O(n) space for n table elements.  In
     addition,  the  table and the hashing function can
     be  constructed in O(n) expected time.  Variations
     of  the  method  that  offer different compromises
     between storage usage and update time are present-
     ed.

Gordon V. Cormack
Department of Computer Science
University of Waterloo
Waterloo, Ontario N2L 3G1

gvcormack@watdaisy.uucp
gvcormack%watdaisy@waterloo.csnet