Re: Hash specifics

oz@nexus.yorku.ca
Fri, 14 Dec 1990 12:27:33 -0500

          From comp.compilers
Related articles
[5 earlier articles]
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)
Re: Hash specifics rfg@ncd.com (1990-12-13)
Re: Hash specifics bart@cs.uoregon.edu (1990-12-13)
Re: Hash specifics roth@resi.rice.edu (1990-12-14)
Re: Hash specifics oz@nexus.yorku.ca (1990-12-14)
Re: Hash specifics plx!plxsun!evan@Sun.COM (1990-12-15)
Re: Hash specifics vern@horse.ee.lbl.gov (1990-12-16)
Re: Hash specifics schmidt@oberkampf.ICS.UCI.EDU (Doug Schmidt) (1990-12-17)
Re: Hash specifics preston@ariel.rice.edu (1990-12-17)
Re: Hash specifics brain@eos.ncsu.edu (1990-12-18)
Re: Hash specifics rfpfeifl@watcgl.uwaterloo.ca (Ron Pfeifle) (1990-12-21)
| List of all articles for this month |
Newsgroups: comp.compilers
From: oz@nexus.yorku.ca
Keywords: design
Organization: York U. Communications Research & Development
References: <9012111913.AA07310@cs-sun-fsa.cpsc.ucalgary.ca> <2977@lupine.NCD.COM>
Date: Fri, 14 Dec 1990 12:27:33 -0500

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]
--

Post a followup to this message

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