|Hashtable alternatives email@example.com (Gwynfa) (2000-07-27)|
|Re: Hashtable alternatives firstname.lastname@example.org (2000-08-04)|
|perfect hashing email@example.com (Preston Briggs) (2000-08-04)|
|Re: perfect hashing firstname.lastname@example.org (Tzvetan Mikov) (2000-08-05)|
|Re: perfect hashing email@example.com (Jan Gray) (2000-08-09)|
|Re: perfect hashing firstname.lastname@example.org (2000-08-10)|
|Re: perfect hashing email@example.com.OZ.AU (2000-08-10)|
|Re: perfect hashing firstname.lastname@example.org (Parzival) (2000-08-10)|
|Re: perfect hashing email@example.com (2000-08-13)|
|[5 later articles]|
|From:||Preston Briggs <firstname.lastname@example.org>|
|Date:||4 Aug 2000 21:36:42 -0400|
|Keywords:||theory, symbols, comment|
The moderator wrote:
[Perfect hashing is sometimes useful for a fixed table of keywords, but
you can't use it for a normal symbol table. -John]
Indeed, I wouldn't use it for keywords.
Consider the typical scanner.
a) Recognize that we have some sort of keyword or identifier
b) See if it's a keyword
c) If not, look it up in the symbol table
If we use perfect hashing for step b, then we'll _always_ find
some entry and have to finish with a string comparison.
E.g., suppose we have the string "preston". We check to see if it's
a keyword. Using perfect hashing, we zip quickly to some entry in
the hash table -- an entry which will contain some keyword --
and then we compare, fail, and proceed to step c.
Alternatively, if we use some sort of conventional hashing,
with a sparse table, we would quickly zip to some entry in the table,
and it would probably be empty, and we could proceed directly to
step c, avoiding the need for the string comparison.
[I agree. I've fooled around with perfect hash generators, but in practice
it makes more sense to load the keywords into the same symbol table as the
regular symbols so you can look up every text token in one try. -John]
Return to the
Search the comp.compilers archives again.