Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!mintaka!spdcc!iecc!compilers-sender
From: oz@nexus.yorku.ca
Newsgroups: comp.compilers
Subject: Re: Hash specifics
Keywords: design
Message-ID: <90Dec14.122745est.6192@nexus.yorku.ca>
Date: 14 Dec 90 17:27:33 GMT
References: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <2977@lupine.NCD.COM>
Sender: compilers-sender@iecc.cambridge.ma.us
Reply-To: oz@nexus.yorku.ca
Organization: York U. Communications Research & Development
Lines: 51
Approved: compilers@iecc.cambridge.ma.us

In article <2977@lupine.NCD.COM> rfg@ncd.com (Ron Guilmette) writes:
>
>As others have already noted, Doug Schmidt wrote a cute program called
>gperf (in C++) which is useful for finding perfect hash functions.

A PD almost-perfect hash generator based on Cicelli's work has been around
since early 80s. I include it below. I have used it successfully in a few
places. Here is the diag output of the program for C keywords: [note that
in this case, it generates a table of 51 entries for 36 keywords]

| Perfect hash function finder, CDH Ver. 2.9
| Start time = Fri Dec 14 12:11:42 1990
| 36 keywords, 21 distinct letters.
| The associated char value limit is 21
| The table size limit is 100
| The search ordering is
|  else double case continue float typeof typedef default
|  const short struct sizeof signed static extern inline int
|  if for enum volatile void while char register do return
|  unsigned __alignof switch auto goto union asm long break
| 
| Success! Associated Char Values Follow:
|  _ =18, a =11, b = 9, c = 1, d = 0, e = 0, f = 3, g = 9, h =15,
|  i = 2, k =21, l =20, m =18, n =12, o =21, r =21, s =10, t = 5, u =21,
|  v =20, w =20,
| Hash min = 4, max = 50, spread = 47
|  else 4, case 5, double 6, if 7, inline 8,
|  continue 9, int 10, const 11, default 12, float 13,
|  typeof 14, typedef 15, signed 16, static 17, extern 18,
|  sizeof 19, short 20, struct 21, enum 22, do 23,
|  void 24, while 25, char 26, for 27, volatile 28,
|  unsigned 29, __alignof 30, switch 31, asm 32, long 33,
|  goto 34, break 35, auto 36, union 38, return 39,
|  register 50,
| 
| Total search invocations = 13727, max depth = 35
|  Started Fri Dec 14 12:11:42 1990
| Finished Fri Dec 14 12:11:47 1990


enjoy...	oz

ps: If you hack this program to look & work nicer, plz drop me a copy.
---
Internet: oz@nexus.yorku.ca, UUCP: utzoo/utai!yunexus!oz
[I have added the perfect hash program to the comp.compilers library,
since it's kind of big to put in a message.  Drop me a line if you want
a copy. -John]
-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.