Java - int WON'T overflow with hashing

Question

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.

Answer 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 g^k using integer arithmetic; e.g. using the recurrence:

g⁰ = 1

g^k = g * g^{k - 1} (for k > 0).