From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: *
X-Spam-Status: No, score=1.1 required=5.0 tests=BAYES_20,INVALID_DATE
	autolearn=no autolearn_force=no version=3.4.4
Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!cmcl2!harvard!husc6!panda!genrad!decvax!decwrl!ucbvax!ICSC.UCI.EDU!mac
From: mac@ICSC.UCI.EDU.UUCP
Newsgroups: net.lang.ada
Subject: Re: Perfect hash function for Ada keywords
Message-ID: <8605141846.AA18967@ucbvax.Berkeley.EDU>
Date: Wed, 14-May-86 15:37:10 EDT
Article-I.D.: ucbvax.8605141846.AA18967
Posted: Wed May 14 15:37:10 1986
Date-Received: Fri, 16-May-86 05:44:10 EDT
References: <12206465628.34.HABERLER@SU-SIERRA.ARPA>
Sender: usenet@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
List-Id: <comp.lang.ada>


The first such mention that I know of is a paper in the July,August 1984
issue of Ada Letters called "A Perfect Hash Function for Ada Reserved Words"
by Dave Wolverton.  This function hashes the 63 Ada reserved into 71 
positions.

Robert W. Sebesta and Mark A. Taylor in their article: "Fast Identification
of Ada and Modula-2 Reserved Words" (Journal of Pascal, Ad, and Modula-2,
March/April 1986), improves Wolverton's algorithm by finding a truly perfect
hash for 63 positions.

While Sebesta and Taylor's algorthm is perfect (and minimal in space 
requirements for a hash table), an even faster method could be used where
a table of twice (or three or four times) the size of a perfect table
could be used. While this requires more space, lookup is faster since a
hash to an empty position can be readily determined, whereas a hash to
a filled position requires a string compare.

		-- Greg Finnegan
		   mac@icsc.uci.edu