Re: Is Minimal Perfect Hashing the wrong algorithm?

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]


--

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