Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!husc6!panda!genrad!decvax!ima!johnl
From: johnl@ima.UUCP (Compilers mailing list)
Newsgroups: mod.compilers
Subject: Re: Query about token mapping
Message-ID: <206@ima.UUCP>
Date: Mon, 8-Sep-86 11:12:17 EDT
Article-I.D.: ima.206
Posted: Mon Sep  8 11:12:17 1986
Date-Received: Tue, 9-Sep-86 00:24:53 EDT
Reply-To: ihnp4!ihdev!pdg
Organization: American Nasal Amputation Centre
Lines: 28
Approved: <compilers@ima.UUCP>
In-Reply-To: <204@ima.UUCP>

Cc:


>There has been a fair amount written on both the form of perfect hash functions
>and methods of computing them, typically by fitting some sort of polynomial.
>Do any of you readers know of good references?  I can't find any right now.

There is a very good (but short) article on reciprocal hashing (a form
of perfect hashing) by G. Jaeschke in Comm ACM, 24,12 (Dec. 1981).  The
article explains advantages of using the reciprocal method to obtain
perfect hash functions and briefly mentions other methods.  References
from this article that may also be useful are: (edited)

1. Cichelli, R.J. Minimal perfect hash functions made simple.
Comm. ACM, 23, 1 (Jan 1980), 17-19.
2. Jaescjke, G. Minimal Perfect Hashing. Tech Rept. TR 80.02.0003
IBM Heidelberg Scientific Center, Niederlassung Heideberg, Germany.
3. Jaeschke, G., Osterburg, G. On Cichelli's minimal perfect hash
functions method.  Comm. ACM, 23, 12 (Dec 1980), 728-729.
4. Knott, G.D. Hashing Functions, Computer J., 18 (Aug 1975), 265-278
5. Sprugnoli, R. Perfect hashing functions: a single probe retrieving
method for static sets. Comm. ACM, 20, 11 (Nov 1977), 841-850.

Paul Guthrie
ihnp4!ihdev!pdg
-- 
Send compilers mail to ima!compilers or, in a pinch to Levine@YALE.EDU
Plausible paths are { ihnp4 | decvax | cbosgd | harvard | yale | bbncca}!ima

Please send responses to the originator of the message -- I cannot forward
mail accidentally sent back to compilers.  Meta-mail to ima!compilers-request