Path: utzoo!utgpu!jarvis.csri.toronto.edu!helios.physics.utoronto.ca!ists!yunexus!oz
From: oz@yunexus.UUCP (Ozan Yigit)
Newsgroups: comp.lang.misc
Subject: Re: Adaptive perfect hashing -- the summary
Keywords: perfect hashing adaptive gperf
Message-ID: <8117@yunexus.UUCP>
Date: 28 Feb 90 22:51:11 GMT
References: <1990Feb10.160605.25254@ux1.cso.uiuc.edu> <4896@brazos.Rice.edu> <1990Feb18.233444.7345@agate.berkeley.edu> <25DF492F.12453@paris.ics.uci.edu> <1990Feb27.234244.24879@agate.berkeley.edu>
Reply-To: oz@yunexus.UUCP (Ozan Yigit)
Organization: York U. Communications Research & Development
Lines: 24

In article <1990Feb27.234244.24879@agate.berkeley.edu> adrianho@cory.Berkeley.EDU (Adrian J Ho) writes:
>Of course, the problem is that gperf only does static perfect hashing, so
>I'll probably have to tear gperf apart, figure out exactly which code does
>what, and then work from there.  Alas, academic pressure precludes doing
>that right now, but I'd love to hear from anyone out there who's doing it
>right now.

The algorithm was described by R.J. Cichelli in The January 1980 issue of
Communications of the ACM under the title "Minimal Perfect Hash Functions
made Simple." Also see "More On Minimal	Perfect Hash tables" by 
Curtis Cook and R. Oldehoeft, a Colorado State University Technical Report.
A very early implementation of this algorithm, (before gperf was ever
written) was done by Charlie Hanever of GenRad, I think around 1984 or
1985. [I still have it someplace]. If I recall correctly, there was also
some discussion about "external perfect hashing" in one of the ACM Trans.
on Database Systems. There is also a UofCalgary (I think) tech report with
bit more implementation detail. I can dig it out if you really want it.

oz
-- 
There are two kinds of fool.   	       	           Internet:  oz@nexus.yorku.ca
One says, "This is old, and therefore good"        Uucp:  uunet!utai!yunexus!oz
And one says "This is new, and therefore Better"   Bitnet: oz@[yulibra|yuyetti]
              John Brunner (The Shockwave Rider)   Phonet: +1 416 736-5257x3976