4

Let's say I want to build a perfect hash table for looking up an array where the predefined keys are 12 Months, thus I would want

hash("January")==0
hash("December")==11

I run my Month names through gperf and got a nice hash function, but it appears to give out 16 buckets(or rather the range is 16)!

#define MIN_HASH_VALUE 3
#define MAX_HASH_VALUE 18
/* maximum key range = 16, duplicates = 0 */

Looking at the generated gperf code, its hash function code does a simple return of len plus char value lookup from a 256 size table. Somehow, in my head I imagined a fancy looking function... :)

What if I want exactly 12 buckets(that is I do not want to skip over unused buckets)? For small sets as this, it really doesn't matter, but when I have 1000 predefined keys and want exactly 1000 buckets in a row?

Can one find a deterministic way to do this?

6
  • 4
    The goal of such hashes is to have a really fast hash function, thus the power of 2 (16 buckets for 12 months, 1024 buckets for your 1000 predefined keys). Why do you want to avoid such holes ? Do you agree to have a performance hit because of this requirement ?
    – Jerome
    Nov 20, 2009 at 14:12
  • Thanks! That explains it then.
    – Sint
    Nov 20, 2009 at 14:14
  • To clarify, reason I asked was that I was looking to replace long "if then else if then else if" chains of strcmp with hashes. A few empty buckets would be a small price to pay, if the speedup is significant.
    – Sint
    Nov 20, 2009 at 14:19
  • One slightly annoying problem with empty buckets is that it means, one has to hand pick buckets for each key(that is I am not sure whether April key points to bucket 3,4,5,6 or 7).
    – Sint
    Nov 20, 2009 at 14:22
  • I really wonder what you need those perfect hashes for; my gut level suspicion is that you're solving a problem you don't really have, or that you have a performance problem and attacking the wrong cause. Of course I could be wrong and would be interested to see what the actual problem is. Nov 20, 2009 at 14:51

3 Answers 3

6

I was interested in the answer to this question & came to it via a search for gperf. I tried gperf, but it was very slow on a large input file and thus did not seem suitable. I tried cmph but I wasn't happy with it. It requires building a file which is then loaded into the C program at run time. Further, the program is so fragile (crashes with "segmentation fault" on any kind of mistaken input) that I did not trust it. A further Google search led me to this page, and onward to mph. I downloaded mph and found it is very nice. It has an optional program to generate a C file, called "emitc", and using it like

 mph < systemdictionaryfile | emitc > output.c

worked almost instantly (a few seconds with a dictionary of about 200,000 words) and created a working C file which compiles with no problems. My tests also indicate that it works. I haven't tested the performance of the hashing algorithm yet though.

1
  • I tried mph 1.2. When using emitc -l, the resulting hash function has a length parameter. That's nice, but the code seems to be broken. The for-loop still searched for a terminating \0. So the code generator is broken, I believe. This is still a very neat tool! And I find it very sad that it seems to be unmaintained.
    – Sven
    May 22, 2020 at 0:52
4

The only alternative to gperf I know is cmph : http://cmph.sourceforge.net/ but, as Jerome said in the comment, having 16 buckets provides you some speed benefit.

When I first looked at minimal perfect hasihing I found very interesting readings on CiteseerX but I resisted the temptation to try coding one of those solutions myself. I know I would end up with an inferior solution respect to gperf or cmph or, even assuming the solution was comparable, I would have to spend a lot of time on it.

1
  • Accepted as answer for providing alternatives and additional information. As for coding a solution oneself, that is always a tempting path down to insanity..
    – Sint
    Nov 23, 2009 at 8:54
0

There are many MPH solutions and algorithms, gerf doesn't yet do MPH's, but I'm working on it. Esp. for large sets. See https://gitlab.com/rurban/gperf/-/tree/hashfuncs

The classic cmph has a lot of constant overhead and is only recommended for huge key sets.

There's the NetBSD nbperf and my improved variant: https://github.com/rurban/nbperf which does CHM, CHM3 and BZD, with integer key support, optimizations for smaller key sets and alternate hash functions.

There's Bob Jenkin's generator, and Taj Khattra's mph-1.2.

There are also two perl libraries to generate C lookups, one in PostgresQL (PerfectHash.pm) and one for late perl5 unicode lookups (regen/mph.pl), and a tool to compare various generators: https://github.com/rurban/Perfect-Hash

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.