* Perfect hash function for Ada keywords
@ 1986-05-13 23:18 HABERLER
1986-05-14 19:37 ` mac
1986-05-16 21:40 ` Jeff Bartlett
0 siblings, 2 replies; 3+ messages in thread
From: HABERLER @ 1986-05-13 23:18 UTC (permalink / raw)
I remember having seen such an animal somewhere but I can't remember where.
Any hints are greatly appreciated.
- michael
-------
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Perfect hash function for Ada keywords
1986-05-13 23:18 Perfect hash function for Ada keywords HABERLER
@ 1986-05-14 19:37 ` mac
1986-05-16 21:40 ` Jeff Bartlett
1 sibling, 0 replies; 3+ messages in thread
From: mac @ 1986-05-14 19:37 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: Perfect hash function for Ada keywords
1986-05-13 23:18 Perfect hash function for Ada keywords HABERLER
1986-05-14 19:37 ` mac
@ 1986-05-16 21:40 ` Jeff Bartlett
1 sibling, 0 replies; 3+ messages in thread
From: Jeff Bartlett @ 1986-05-16 21:40 UTC (permalink / raw)
> 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.
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~1986-05-16 21:40 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1986-05-13 23:18 Perfect hash function for Ada keywords HABERLER
1986-05-14 19:37 ` mac
1986-05-16 21:40 ` Jeff Bartlett
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox