|Is Minimal Perfect Hashing the wrong algorithm? email@example.com (Charles Fiterman) (1996-04-02)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? firstname.lastname@example.org.OZ.AU (1996-04-04)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? email@example.com (1996-04-06)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? firstname.lastname@example.org (Alexander Krotoff) (1996-04-07)|
|Is Minimal Perfect Hashing the wrong algorithm? email@example.com (1996-04-08)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? firstname.lastname@example.org (Dave Lloyd) (1996-04-08)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? email@example.com (1996-04-10)|
|Re: Is Minimal Perfect Hashing the wrong algorithm? firstname.lastname@example.org (Dave Toland) (1996-04-11)|
|From:||Alexander Krotoff <email@example.com>|
|Date:||7 Apr 1996 23:58:15 -0400|
|Organization:||Research Computer Center, Moscow State University|
2 Apr 1996 23:36:51 -0500 Charles Fiterman wrote:
> Many compiler writers use Minimal Perfect Hashing to generate some
> hash tables such as a key word table.
Yes, they do. But, this method is often used to recognize keywords
in the stream of identifiers, which are lexicaly often has the same
form as keywords.
> 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?
It depends on the form of MPHF used and hashing strategy. For example
Chang-Lee (?) method may build MPHF on the top of another hash
function which is used to hash all identifiers.
If anybody is interested I may send my own implementation of this
method. It succesfuly builds MPHF for up to 2000 words on the 32-bit
> 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.
No. As seems to me it is extremely time-expensive to build MPHF in the
compile-time for _all_ identifiers.
Alexander N. Krotoff firstname.lastname@example.org
Research Computer Center tel: +7(095)939-2638
Moscow State University fax: +7(095)939-4430
Return to the
Search the comp.compilers archives again.