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

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? 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
cousin?
--
det@enterprise.sw.stratus.com
(Dave Toland)
--

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