Re: Is Minimal Perfect Hashing the wrong algorithm?

Alexander Krotoff <krotoff@boy.nmd.msu.ru>
7 Apr 1996 23:58:15 -0400

          From comp.compilers

Related articles
Is Minimal Perfect Hashing the wrong algorithm? cef@geodesic.com (Charles Fiterman) (1996-04-02)
Re: Is Minimal Perfect Hashing the wrong algorithm? fjh@cs.mu.OZ.AU (1996-04-04)
Re: Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-06)
Re: Is Minimal Perfect Hashing the wrong algorithm? krotoff@boy.nmd.msu.ru (Alexander Krotoff) (1996-04-07)
Is Minimal Perfect Hashing the wrong algorithm? preston@tera.com (1996-04-08)
Re: Is Minimal Perfect Hashing the wrong algorithm? dave@occl-cam.demon.co.uk (Dave Lloyd) (1996-04-08)
Re: Is Minimal Perfect Hashing the wrong algorithm? yuen@elec.uq.oz.au (1996-04-10)
Re: Is Minimal Perfect Hashing the wrong algorithm? det@platsol.com (Dave Toland) (1996-04-11)
| List of all articles for this month |

From: Alexander Krotoff <krotoff@boy.nmd.msu.ru>
Newsgroups: comp.compilers
Date: 7 Apr 1996 23:58:15 -0400
Organization: Research Computer Center, Moscow State University
References: 96-04-012
Keywords: theory

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


Post a followup to this message

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