'Java - int WON'T overflow with hashing

So I'm just getting into Object-Oriented Programming in Java, and I have to make this hashed dictionary. I'm supposed to hash a name with a algorithm and return the hashed value. The lab said to do

int n = s.length();
for (int i = 0; i < n; i++)
hash = g * hash + s.charAt(i);

where g = 31, s = firstName + lastName;

and I looked at this and put it into code. What I wrote was

public int hashCode()     // part of the Name class
{
    int h = 0;
    String bothNames = first + last;
    for (int i = 0; i < bothNames.length(); i++) {
        h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1);
    }
    return h;
}

Now, when I ran this code on something like Name testName = new Name("Wayne", "Gretzky"); and printed out testName.hashCode(), I almost always got the 32 bit integer limit back, which meant that it wasn't overflowing. However, when I changed the for loop to

for (int i = 0; i < bothNames.length(); i++) {
    h = g*h + bothNames.charAt(i);
}

all of a sudden, it was overflowing again. I don't really understand why this would happen. The two hash functions should be the same. Why wouldn't h overflow in the first case? Thanks in advance.

javahashoverflowhashcode


Solution 1:[1]

The problem is this:

h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1)

The pow method is returning a large double value. Which you multiply by an integer to give you a larger double value. Then the h += ... does a primitive narrowing conversion from double to int.

The double to int conversion is defined to convert any floating point value value greater than Integer.MAX_VALUE to Integer.MAX_VALUE (!).

The solution will be to compute the gk using integer arithmetic; e.g. using the recurrence:

g0 = 1

gk = g * gk - 1 (for k > 0).

Solution 2:[2]

Let's look at the following line:

h += bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1);

Considering the nature of compound assignment operators, this is equivalent to:

h = (int)(h + (bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1)));

This would be fine, if it were not for the fact that Math.pow returns a double. Taking regular widening rules into account:

h = (int)(intValue + (intValue * doubleValue))
h = (int)(intValue + doubleValue)
h = (int)(doubleValue)

The last doubleValue gets narrowed to an int. If the string is long enough, the doubleValue will exceed Integer.MAX_VALUE from the first iteration.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Stephen C
Solution 2 Robby Cornelissen

Related Questions