Re: Is Minimal Perfect Hashing the wrong algorithm?

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


> 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 krotoff@such.srcc.msu.su
Research Computer Center tel: +7(095)939-2638
Moscow State University fax: +7(095)939-4430
--

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