Perfect hash function for Ada keywords

Perfect hash function for Ada keywords

[HABERLER]

I remember having seen such an animal somewhere but I can't remember where.
Any hints are greatly appreciated.

- michael
-------

Re: Perfect hash function for Ada keywords

[mac]

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

Re: Perfect hash function for Ada keywords

[Jeff Bartlett]

> I remember having seen such an animal somewhere but I can't remember where.
> Any hints are greatly appreciated.
> 
> - michael
> -------

See Ada Letters, vol IV, number 1 July,August 1984, p. 40.

Jeff Bartlett
Center for Digital Systems Research
Research Triangle Institute				rti-sel!jb@mcnc

P.S.  I have it in C and Yacc if your interested.