Link to home
Start Free TrialLog in
Avatar of shampouya
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;
}

Open in new window

Avatar of d-glitch
d-glitch
Flag of United States of America image

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

There are   27³ = 19,683 possibilities.
SOLUTION
Avatar of TommySzalapski
TommySzalapski
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of shampouya
shampouya

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?
ASKER CERTIFIED SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
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.
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
Sorry. I was doing it backward.
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.
thanks a lot guys