# Re: Is Minimal Perfect Hashing the wrong algorithm?

## Dave Toland <det@platsol.com>11 Apr 1996 23:41:01 -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: Dave Toland Newsgroups: comp.compilers Date: 11 Apr 1996 23:41:01 -0400 Organization: Locus Computing Corp. References: 96-04-012 96-04-031 Keywords: symbols

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
--

Post a followup to this message