Re: Is Minimal Perfect Hashing the wrong algorithm?

fjh@cs.mu.OZ.AU
4 Apr 1996 00:22:29 -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: fjh@cs.mu.OZ.AU
Newsgroups: comp.compilers
Date: 4 Apr 1996 00:22:29 -0500
Organization: Compilers Central
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.


Do they? GNU C uses `gperf', which generates non-minimal perfect
hashing functions.


>But this algorithm minimizes table size. Shouldn't it minimize lookup
>time with a cap on table size? That is shouldn't it look at the time
>required to create a hash from an entry?


Yes.


>And in this light maybe synonyms aren't so bad if the second entry in
>the bucket is something rare and misses are also rare.


But even then, you must still check for collisions, and the cost of
checking for collisions must be paid on every lookup, not just on
those few for which a collision is encountered.


Incidentally, a related issue is generating hash tables when compiling
programs, rather than when building the compiler. This is useful if
the language you are compiling on has a switch statement (or
equivalent) that can switch on strings. For this, you almost
definitely don't want to use minimal perfect hashing most of the time,
since the search for a minimal perfect hash function can take a long
time, and you don't want compilation to be too slow. (I wrote the
part of the Mercury compiler which handles string switches; it
generates hash tables using open addressing.)


--
Fergus Henderson <fjh@cs.mu.oz.au>
WWW: <http://www.cs.mu.oz.au/~fjh>
PGP: finger fjh@128.250.37.3
--


Post a followup to this message

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