CODEWITHSUNDEEP
data-structureshash
jpro
jpro

Reputation: 25

Hash Function Overflow

In my class of data structure we are learning different hash functions, but this one in particular I do not understand why in the last three lines of the code they check if HashVal<0, because since HashVal is the reminder of division for tableSize it should never be less than zero. Please I just want to understand this last part. Thank you in advance. 

public static 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;

if( hashVal < 0 ) //overflow case

   hashVal += tableSize;

return hashVal;

}

Upvotes: 0

Views: 1971

Answers (2)

Artem
Artem

Reputation: 7423

int in Java is signed 32-bit data type. Therefore, maximum value which it can store is 2^31-1 which is MAX_VALUE constant in Integer class. Based on negative number representation (left bit is a sign bit) once a number is more than MAX_VALUE it will become negative based on that representation.

Upvotes: 2

SCaffrey
SCaffrey

Reputation: 341

hashVal is a int, and it has a maximum size. If the length of the string is long enough, the hashVal becomes really big because you've multiplied it by 37 for many times, and it overflows. When it overflows, it might become a negative number, so you need to check the result if hashVal is negative.

There is also a known way to solve this. Change

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

into 

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

Upvotes: 1

Related Questions