shampouya
asked on
Is this an even distribution of hash values?
In the hash function code below why doesn't line 5 say this:
hashVal = hashVal + 37 * key.charAt(i);
instead of this:
hashVal = 37 * hashVal + key.charAt(i);
hashVal = hashVal + 37 * key.charAt(i);
instead of this:
hashVal = 37 * hashVal + key.charAt(i);
public static int hash3(String key, int tableSize) {
int hashVal = 0;
for (int i = 0; i < key.length(); i++) {
hashVal = 37 * hashVal + key.charAt(i);
}
hashVal %= tableSize;
if (hashVal < 0) {
hashVal += tableSize;
}
return hashVal;
}
If it used "hashVal = hashVal + 37 * key.charAt(i)", what would the effect be on the hash? Let's say the table was a million entries big, what would the hash look like for "Hello World!"?
Same question with the chosen line: hashVal = 37 * hashVal + key.charAt(i);
David
Same question with the chosen line: hashVal = 37 * hashVal + key.charAt(i);
David
ASKER
But hashVal = hashVal + 37 * key.charAt(i); would ensure that no two strings would have the same hash value, right? Isn't that the goal? I'm not sure where the conflict is.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ozo's point is much more to the point. My point is rather esoteric and misses the point. ;-) If you still don't "get" his answer, just work it out on paper.
David
David
ASKER
thanks
hashVal = hashVal + 37 * key.charAt(i);
would mean that swapping key.charAt(1) and key.charAt(2) would leave the hash value unchanged
whereas
hashVal = 37 * hashVal + key.charAt(i);
would cause different keys to have different hash values (at least until the %= tableSize)
and as long as no two charAt values differ by 37