Is Minimal Perfect Hashing the wrong algorithm? - comp.compilers #9199

Dave Toland <>
4 Apr 1996 00:20:15 -0500

          From comp.compilers

Related articles
Is Minimal Perfect Hashing the wrong algorithm? (Charles Fiterman) (1996-04-02)
Is Minimal Perfect Hashing the wrong algorithm? - comp.compilers #9199 (Dave Toland) (1996-04-04)
| List of all articles for this month |

From: Dave Toland <>
Newsgroups: comp.compilers
Date: 4 Apr 1996 00:20:15 -0500
Organization: Compilers Central
References: 96-04-012
Keywords: theory

Charles Fiterman <> 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? That is shouldn't it look at the time
> required to create a hash from an entry?
> 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.

With an increasing penalty on random memory accesses relative to cache
accesses and processor operations, the single probe nature of MPH is
even more of a win than before. On the other hand, character weight
tables also add to the cost of an MPH access, so there are indeed
trade-offs that need to be examined for each application, and they may
change dramatically when ported to different host platforms.

However, how often is an MPH a worse performer than its non-minimal
(Dave Toland)

Post a followup to this message

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