Re: Perfect hash function for Ada keywords

[mac@ICSC.UCI.EDU.UUCP]

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