Re: Perfect Hashfunctions
On Nov 12, 9:44 pm, "Johannes Schaub (litb)" <schaub-johan...@web.de>
wrote:
I want to learn how to create perfect hash functions for switch statement=
s
over strings. So given
switch(str) {
case str1...
case str2...
...
case strN...
}
I don't understand the example. Why are you worried about switch
statements? As far as I know, the term 'perfect hash' refers to
a mapping between strings and integers. And the switch statement
gives you a mapping between integers and code sequences.
Would this pseudocode more accurately reflect what you want?
enum { str1, str2, str3, ..., strN };
ph = makeperfecthash(set of strings)
....
switch (applyhash(ph, str)) {
case str1: ...
case str2: ...
...
case strN: ...
}
There are at least 2 pieces: building (or picking) the hash
function which will perform perfectly over a known set of
strings, and actually executing that hash for a specific
string to get a specific integer.
I want to create a perfect hash function that gives me an unique integer =
for
each of those strI, in the range of [0 ... M] (M should preferably be
small).
and candy-coated. ;)
However, I can't for the life of me find any tutorial or documentation on
how to build up such a function. All I find are statements that I can use=
a
two-stage hashing system, and use a certain function for the first stage =
and
then for the second stage finding the function from a set of "universal
hashing functions" by randomly testing whether a given function will be
perfect. This sounds like "let's try randomly, and if there is no functio=
n
that works, we are just shit-outta-luck"
Well, yeah. What did you expect?
I have no idea what an universal hashing function really is about and
whether that is the only way of creating a perfect hash function, too: I
read about CHD, BDZ, BMZ, CHM, BRZ and FCH on the page of cmph, but I've =
no
clue how they relate to the big picture.
This part is out of my league.
Can anyone shed some light on this, please? Is it really difficult to do =
a
perfect hashing?
If I haven't shed any light on the real issue,
hopefully I've helped clarify the question.
--
Do not trouble me with Faramir,
I know his uses and they are few.