HABERLER@SU-SIERRA.ARPA.UUCP (05/14/86)
I remember having seen such an animal somewhere but I can't remember where. Any hints are greatly appreciated. - michael -------
mac@ICSC.UCI.EDU.UUCP (05/14/86)
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
jb@rti-sel.UUCP (Jeff Bartlett) (05/17/86)
> 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.