Re: Hash specifics (John R. Levine)
11 Dec 90 15:12:51 EST (Tue)

          From comp.compilers

Related articles
Hash specifics (1990-12-11)
Re: Hash specifics (1990-12-11)
Re: Hash specifics chased@Eng.Sun.COM (1990-12-11)
Re: Hash specifics (1990-12-11)
Re: Hash specifics (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 (1990-12-13)
[10 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: (John R. Levine)
In-Reply-To: <>
Keywords: design, bibliography
Organization: I.E.C.C.
Date: 11 Dec 90 15:12:51 EST (Tue)

In article <> 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.

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.
John Levine,, {spdcc|ima|world}!iecc!johnl

Post a followup to this message

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