perfect hashing

Preston Briggs <preston@tera.com>
4 Aug 2000 21:36:42 -0400

          From comp.compilers

Related articles
Hashtable alternatives gwynfa@paradise.net.nz (Gwynfa) (2000-07-27)
Re: Hashtable alternatives rkrayhawk@aol.com (2000-08-04)
perfect hashing preston@tera.com (Preston Briggs) (2000-08-04)
Re: perfect hashing ceco@jupiter.com (Tzvetan Mikov) (2000-08-05)
Re: perfect hashing jsgray@acm.org (Jan Gray) (2000-08-09)
Re: perfect hashing jmochel@foliage.com (2000-08-10)
Re: perfect hashing fjh@cs.mu.OZ.AU (2000-08-10)
Re: perfect hashing parz@home.com (Parzival) (2000-08-10)
Re: perfect hashing rick@home.com (2000-08-13)
[5 later articles]
| List of all articles for this month |

From: Preston Briggs <preston@tera.com>
Newsgroups: comp.compilers
Date: 4 Aug 2000 21:36:42 -0400
Organization: Compilers Central
References: 00-07-064 00-08-022
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.


Preston
[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]


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.