CODEWITHSUNDEEP
chash
MetallicPriest
MetallicPriest

Reputation: 30805

A perfect hash for known values

Say I have some known values, against which I want to create a hash table. For example,

For 0x78409 -> 1
For 0x89934 -> 2
For 0x89834 -> 3

etc...

But these values (0x78409, 0x89934, 0x89834) are only known at runtime, so switch/case cannot be used. However, they become known at the beginning of execution, so maybe we can create a hash function which adapts itself to make a perfect hash table. So my question is, can we create a perfect hash function for such case.

Upvotes: 4

Views: 1059

Answers (2)

Necrolis
Necrolis

Reputation: 26171

If the entire domain of inputs is known before the hashmap is created, then this is possible, but requires some form of runtime code generation, either via a VM or JIT (probably through a scripting language, such as LuaJIT), that would allow you to use gperf and its ilk to create a hash at runtime, compile it, then use it to fill and retrieve from the map.

An easier, more viable solution is to use a hash function with extremely low collisions for the given set of input permutations (ie: you might only be using alphabetical, lowercase characters for instance), a minimal perfect hash.

Murmur3 and crapwow are the ones to lookout for (though, I'd be cautious with crapwow), Google's CityHash, and xxHash are also worth looking at. Bob Jenkins also has a good minimal perfect hash based map available here, which should do just fine as well.

Upvotes: 3

Basile Starynkevitch
Basile Starynkevitch

Reputation: 1

Wikipedia gives this page. But are you sure you want a perfect hash function? Perhaps a good and fast hash function can be enough?

Upvotes: 1

Related Questions