We help IT Professionals succeed at work.

# Is this an even distribution of hash values?

on
In the hash function code below why doesn't line 5 say this:

hashVal = hashVal + 37 * key.charAt(i);

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;
}
``````
Comment
Watch Question

## View Solution Only

Most Valuable Expert 2014
Top Expert 2015

Commented:

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
Software Developer
Top Expert 2006

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

Commented:
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.
Most Valuable Expert 2014
Top Expert 2015
Commented:
hashVal = hashVal + 37 * key.charAt(i)
would ensure that "ab" and "ba" would have the same hash value
hashVal = 37 * hashVal + key.charAt(i);
would cause "ab" and "ba" to have different hash values.
(unless tableSize was a factor of 36)
Software Developer
Top Expert 2006

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

Commented:
thanks