|Is Minimal Perfect Hashing the wrong algorithm? email@example.com (Charles Fiterman) (1996-04-02)|
|Is Minimal Perfect Hashing the wrong algorithm? - comp.compilers #9199 firstname.lastname@example.org (Dave Toland) (1996-04-04)|
|From:||Dave Toland <email@example.com>|
|Date:||4 Apr 1996 00:20:15 -0500|
Charles Fiterman <firstname.lastname@example.org> 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
Return to the
Search the comp.compilers archives again.