CODEWITHSUNDEEP
chashtablegnulookup-tables
Sint
Sint

Reputation: 1620

Making a perfect hash (all consecutive buckets full), gperf or alternatives?

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?

Upvotes: 4

Views: 4031

Answers (3)

rurban
rurban

Reputation: 4131

There are many MPH solutions and algorithms, gperf 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. Fixed version: https://github.com/rurban/cmph

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

Upvotes: 2

user181548
user181548

Reputation:

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.

Upvotes: 6

Remo.D
Remo.D

Reputation: 16522

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.

Upvotes: 4

Related Questions