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.

CodePudding user response：

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

CodePudding user response：

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.