Perfect Hash Function for Perl (like gperf)?

Question

I'm going to be using a key:value store and would like to create non-collidable hashes in Perl. Is there a Perl module, or function that I can use to generate a non-collidable hash function or table (maybe something like gperf)? I already know my range of input values.

Answer 1

I can't find a pure Perl solution, closest is Reini Urban's examinations of using perfect hashes with a type system. If you were to do it in XS, the CMPH (C Minimal Perfect Hashing Library) might be more apropos than gperf. CMPH seems to be optimized for non-trivial key sizes and run-time generation.

The cost of generating a perfect hash function at runtime in Perl might swamp the value of using it. In order to gain benefit, you'd want it compiled and cached. So again, writing an XS module which generates the function from a fixed key list at XS compile time might be the best way to go.

Out of curiosity, how big is your data and how many keys does the set contain?

Answer 2

You might be interested in Judy. It's not a hash table implementation, but it's supposedly a very efficient associative array implementation.

Mind you, Perl's hashes are very well tuned, and they automatically get rehashed when a bucket starts growing large.