Re: Is Minimal Perfect Hashing the wrong algorithm?

preston@tera.com (Preston Briggs)
6 Apr 1996 22:14:35 -0500

          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: 6 Apr 1996 22:14:35 -0500
Organization: /etc/organization
References: 96-04-012
Keywords: theory

Charles Fiterman <cef@geodesic.com> writes:
>Many compiler writers use Minimal Perfect Hashing to generate some
>hash tables such as a key word table.
>But this algorithm minimizes table size. Shouldn't it minimize lookup
>time with a cap on table size?


I think it's even worse than you suggest. Given some unknown
alphabetic token, we first look in this minimal table to see if it's a
keyword. If it isn't, we assume it's an identifier. Since the
minimal table is dense, every identifier will collide with some
keyword and we'll have to do a string compare to resolve the question
of "keyword or id?"


If I hashed keywords, I'd make the table very sparse. Then most
identifiers would hash to an empty location and no string compare
would be required.


The cost in space would be pretty minimal. Imagine a language with 50
keywords. If the hash table is an array of 4-byte pointers to
strings, then a 1 Kbyte table would get the density down to 20%.


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


--


Post a followup to this message

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