Any idea why this hash function is returning negative values?

[garywoot]

I can't trace the code because if I use system.out.print within the while loop my computer just freezes ...

it seems that the hash value is positive UNTIL the actual polynomial accumulation (hashVal=37*hashVal+key.charAt(i)). I have no idea why this would be. My input would be something like key = "kajwehlfkhj", and the ASCII that coressponds to each letter is not negative at all...


public int hash( String key, int tableSize )
{
int hashVal = 0;

for( int i = 0; i < key.length( ); i++ )
hashVal = 37 * hashVal + key.charAt( i );

hashVal %= tableSize;
return hashVal;
}

[Insectoid]

How big is hashVal going to be at the end of the for loop but before the modulus for the string "AAAAAAA"? What happens when an integer gets that big?

[C14]

Quote:

What happens when an integer gets that big?

I figure the same thing, you are exceeding the limit of an integer

[garywoot]

Never knew an integer just becomes negative when you exceed its size... would have figured java would throw an exception or something, lol.

[DemonWasp]

This is called "overflow" (see http://en.wikipedia.org/wiki/Arithmetic_overflow), and the way it gets handled varies by platform. Java defines that overflow operates in a particular way (positive wraps to negative) which is a consequence of the "two's complement" arithmetic system (http://en.wikipedia.org/wiki/Two's_complement) used by the most popular CPUs.

Arithmetic operations in Java do not throw exceptions, except in the case of integer divide-by-zero. Floating-point divide-by-zero operations succeed because they follow the IEEE 754 specification, which results in either +Infinity, -Infinity, or NaN.

[crossley7]

Generally the more widely used languages choose not to throw an exception and just handle it natively because the time required to check for overflow on every arithmetic operation would drastically reduce the speed of the program and so they leave the checking to the user for overflow.