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

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

ozo

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

anyoneis

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

shampouya

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

ozo

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

anyoneis

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

shampouya

ASKER

thanks