We help IT Professionals succeed at work.

Is this an even distribution of hash values?

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

Open in new window

Comment
Watch Question

ozo
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
anyoneisSoftware 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

Author

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)
anyoneisSoftware 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

Author

Commented:
thanks