We help IT Professionals succeed at work.

Why is this constant being used in this simple hash function?

shampouya
shampouya asked
on
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;
}

Open in new window

Comment
Watch Question

They are representing 3 character string as a 3 digit number in base 27.

There are   27³ = 19,683 possibilities.
Awarded 2010
Top Expert 2013
Commented:
They are making a hash. Since there are 27 possible letters, then you multiply the value of the first letter by 27*27 (which is 729) and the second by 27. That way every three letter string maps to a different integer value and there's no wasted space.

Author

Commented:
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?
Most Valuable Expert 2014
Top Expert 2015
Commented:
with 15, pa and ab would have the same value, since you increase the *15 place by 1 and decrease the *1 place by 15
with 27 this is not possible
Awarded 2010
Top Expert 2013

Commented:
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.

Author

Commented:
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
Awarded 2010
Top Expert 2013

Commented:
Sorry. I was doing it backward.
pa and ab are what I meant to say.
Awarded 2010
Top Expert 2013

Commented:
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.

Author

Commented:
thanks a lot guys