Is Minimal Perfect Hashing the wrong algorithm?

preston@tera.com (Preston Briggs)
8 Apr 1996 00:02:37 -0400

          From comp.compilers

Related articles
Is Minimal Perfect Hashing the wrong algorithm? cef@geodesic.com (Charles Fiterman) (1996-04-02)
Re: Is Minimal Perfect Hashing the wrong algorithm? fjh@cs.mu.OZ.AU (1996-04-04)
Re: Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-06)
Re: Is Minimal Perfect Hashing the wrong algorithm? krotoff@boy.nmd.msu.ru (Alexander Krotoff) (1996-04-07)
Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-08)
Re: Is Minimal Perfect Hashing the wrong algorithm? dave@occl-cam.demon.co.uk (Dave Lloyd) (1996-04-08)
Re: Is Minimal Perfect Hashing the wrong algorithm? yuen@elec.uq.oz.au (1996-04-10)
Re: Is Minimal Perfect Hashing the wrong algorithm? det@platsol.com (Dave Toland) (1996-04-11)
| List of all articles for this month |

From: preston@tera.com (Preston Briggs)
Newsgroups: comp.compilers
Date: 8 Apr 1996 00:02:37 -0400
Organization: Compilers Central
References: 96-04-012 96-04-031
Keywords: theory

>[I just stick the keywords in the symbol table so with one probe I've got
>whatever it is. I thought that was what everyone did. -John]


Nope. There's this whole group of people out there who use "minimal
perfect hashing" to distinguish keywords from each other and from
other identifiers. They maintain a small hash table with their 50 (or
whatever) keywords stuck in it. When the lexer comes up with an
alphabetic string, they first look in the keyword hash table. If that
lookup fails, then they know they've got an identifier and add it to
the symbol table.


Consider the original message:
>Many compiler writers use Minimal Perfect Hashing to generate some
>hash tables such as a key word table.
>But this algorithm minimizes table size.


I think it's sort of a dumb way to go, as I argued in my previous post.


Other people do like John suggests. Still other people (e.g., Fraser
and Hanson) build a small, hard-coded tree to distinguish keywords as
part of the lexer. That way they avoid any lookups at all for
keywords.


Preston Briggs
--


Post a followup to this message

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