Programming C, C++, Java, PHP, Ruby, Turing, VB
Computer Science Canada 
Programming C, C++, Java, PHP, Ruby, Turing, VB  

Username:   Password: 
 RegisterRegister   
 Any idea why this hash function is returning negative values?
Index -> General Programming
View previous topic Printable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic
Author Message
garywoot




PostPosted: Mon Oct 07, 2013 7:30 am   Post subject: Any idea why this hash function is returning negative values?

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;
}
Sponsor
Sponsor
Sponsor
sponsor
Insectoid




PostPosted: Mon Oct 07, 2013 8:42 am   Post subject: RE:Any idea why this hash function is returning negative values?

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




PostPosted: Wed Oct 09, 2013 8:48 am   Post subject: Re: RE:Any idea why this hash function is returning negative values?

Quote:
What happens when an integer gets that big?


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




PostPosted: Wed Oct 09, 2013 5:31 pm   Post subject: RE:Any idea why this hash function is returning negative values?

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




PostPosted: Wed Oct 09, 2013 6:15 pm   Post subject: RE:Any idea why this hash function is returning negative values?

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




PostPosted: Wed Oct 09, 2013 10:34 pm   Post subject: RE:Any idea why this hash function is returning negative values?

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.
Display posts from previous:   
   Index -> General Programming
View previous topic Tell A FriendPrintable versionDownload TopicSubscribe to this topicPrivate MessagesRefresh page View next topic

Page 1 of 1  [ 6 Posts ]
Jump to:   


Style:  
Search: