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.


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

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