Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site loral.UUCP
Path: utzoo!watmath!clyde!bonnie!akgua!sdcsvax!sdcc6!loral!ian
From: ian@loral.UUCP (Ian Kaplan)
Newsgroups: net.lang.pascal
Subject: Re: Hash function for Pascal keywords?
Message-ID: <572@loral.UUCP>
Date: Fri, 19-Oct-84 21:40:16 EDT
Article-I.D.: loral.572
Posted: Fri Oct 19 21:40:16 1984
Date-Received: Tue, 23-Oct-84 01:07:31 EDT
References: <2487@dartvax.UUCP>
Organization: Loral Instruments, San Diego
Lines: 47


   There is a minimal perfect Hash function for Pascal reserved words.  
   This is described in 
   
     "A Letter Oriented Minimal Perfect Hashing Function" 
     SigPlan Notices, Sept. 1982, V17, #9 
     by Curtis R. Cook and R.R. Oldehoeft.  
     
   This article describes the hash function and the hash table
   organization for a Pascal hash table.  Cook et al's algorithm for finding 
   a perfect hashing function is based on Cichelli's hash function described 
   in 
   
     "Minimal Perfect Hash Functions Made Simple" 
     CACM Jan. 1980, V21, #1.
     by Richard J. Cichelli

   While the Cichelli algorithm works for the reserved words in Pascal (and
   UCSD Pascal) it fails to find a minimal perfect hash function for the 
   reserved words in Modula-2.  

   I modified the algorithm developed by Cook and Oldehoeft so that it
   terminates when it can not find a perfect minimal hash table.
   Unfortunately I do not have it in UNIX readable form.  If you want a
   copy send me email and I can US mail you a Xerox of the listing.

   The generality of the Cichelli hash function is discussed in 
   
     "A Monte Carlo Study of Cichelli Hash-function Solvability" 
     CACM Nov. 1983, V26, #11 pg. 924.  
     R. Charles Bell and Bryan Floyd
   
   There is also an article titled 
   
     "The Study of an Ordered Minimal Perfect Hashing Scheme", 
     CACM April 1984, pg. 384, 
     by C.C.  Chang.  
    
   Mr. Chang claims to have an algorithm which will find minimal
   perfect hashing algorithms without hueristic search (used by the
   Cichelli algorithm).  I do not understand this algorithm.  Perhaps a 
   wiser head would post a tutorial on how Mr. Chang's algorithm works.

                             Ian Kaplan
			     Loral Data Flow Group
			     Loral Instrumentation
			     ucbvax!sdcsvax!sdcc6!loral!ian