shampouya
asked on
Why is this constant being used in this simple hash function?
My textbook is assuming that a three-character String key is being input into this hash function. I understand that there are 26 letters in the alphabet + 1 possible blank, but why is this program multiplying the second and third characters by 27 and 729? Is this just an arbitrary way to generate a hash value?
public static int hash(String key, int tableSize)
{
return (key.charAt(0) + 27 * key.charAt(1) + 729 * key.charAt(2)) % tableSize;
}
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
How does using 27 and 27^2 ensure that every 3-letter string maps to a different hash value?
Playing devil's advocate, why couldn't we just use 15 and 15^2? I know that 15 is a random number but wouldn't that be just as effective at assigning hash values to the input string?
Playing devil's advocate, why couldn't we just use 15 and 15^2? I know that 15 is a random number but wouldn't that be just as effective at assigning hash values to the input string?
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Let's consider strings of length 2. If you encode the string ba (assuming a is 1 and b is 2) then if you are using 15 you will end up with 2*15 + 1 which is 31. But the string ap would be 1*15+16 which also is 31.
If you multiply by 27, then aa is 1*27 + 1 or 28. There is no other way to get this.
Because there are 27 possible letters, then 27 is the magic number that works most efficiently.
If you multiply by 27, then aa is 1*27 + 1 or 28. There is no other way to get this.
Because there are 27 possible letters, then 27 is the magic number that works most efficiently.
ASKER
I can see how pa and ap yield the same value (31) when I use 15, but ba and ap seem to be different, no?
ba
return (2 + 15 * 1) = 17
ap
return (1 + 15 * 16) = 241
ba
return (2 + 15 * 1) = 17
ap
return (1 + 15 * 16) = 241
Sorry. I was doing it backward.
pa and ab are what I meant to say.
pa and ab are what I meant to say.
Usually the digit or character on the left has the highest value. I didn't notice yours was the other way until after I posted and saw Ozo's post. We are saying the same thing. She just reads better than I do.
ASKER
thanks a lot guys
There are 27³ = 19,683 possibilities.