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?


Preston Briggs wrote:
> 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?"


Very true, if you use this probe for every identifier you encounter.
On the other hand it does work very well for assemblers or other
translators where your lexer has enough context knowledge that it
expects/requires a keyword when it is in a particular state.


On the third hand :-), It still doesn't buy you much over an open hash
shared with the dynamic symbols provided your table is sufficiently
large to make keyword collisions unlikely, unless you are unlucky
enough to have collisions on frequently used keywords. But you don't
need perfect hash to tune around that.
--
Dave Toland det@locus.com
--

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