Re: Hash specifics

johnl@iecc.cambridge.ma.us (John R. Levine)
11 Dec 90 15:12:51 EST (Tue)

          From comp.compilers
Related articles
Hash specifics degroot@cpsc.ucalgary.ca (1990-12-11)
Re: Hash specifics johnl@iecc.cambridge.ma.us (1990-12-11)
Re: Hash specifics chased@Eng.Sun.COM (1990-12-11)
Re: Hash specifics pardo@cs.washington.edu (1990-12-11)
Re: Hash specifics henry@zoo.toronto.edu (1990-12-12)
Re: Hash specifics baxter@zola.ICS.UCI.EDU (Ira Baxter) (1990-12-13)
Re: Hash specifics lupine!rfg@uunet.UU.NET (1990-12-13)
Re: Hash specifics rfg@ncd.com (1990-12-13)
[10 later articles]
| List of all articles for this month |
Newsgroups: comp.compilers
From: johnl@iecc.cambridge.ma.us (John R. Levine)
In-Reply-To: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca>
Keywords: design, bibliography
Organization: I.E.C.C.
Date: 11 Dec 90 15:12:51 EST (Tue)

In article <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> you write:
>How does one build a hash function with minimal table size and minimal
>collisions for a known set of hash strings?


The problem of designing a hash algorithm that maps N identifiers into
unique slots in an N entry table is known as perfect hashing. It has been
studied sporadically over the years. There are algorithms known, but they
are all very slow. Here are some references:


R. J. Cichelli, "Minimal perfect hash functions made simple," CACM 23:1,
Jan 1980, pp 17-19.


G. Jaeschke et al., comment on article above, CACM 23:12, Dec 1980, pp.
728-729.


G. Jaeschke, "Reciprocal hashing: a method for generating minimal perfect
hash functions," CACM 24:12, Dec 1981, pp. 829-833.


R. Sprugnoli, "Perfect hashing functions: a single probe retrieving method
for static sets," CACM 20:11, Nov 1977, pp. 841-850.


A brief visit to my 40 shelf-feet of computer journals didn't turn up
anything more recent except for some data base applications. If someone
has a breakthrough in perfect hashing to report, I'd love to hear about it.
--
Regards,
John Levine, johnl@iecc.cambridge.ma.us, {spdcc|ima|world}!iecc!johnl
--

Post a followup to this message

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