Hash Function Overflow

Question

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;

}

hashVal is a int, and it might overflow to become a negative number. — SCaffrey
– SCaffrey, Commented Mar 6, 2016 at 1:10

Artem · Accepted Answer · 2016-03-06 01:21:59Z

2

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.

answered Mar 6, 2016 at 1:21

Artem

7,49315 gold badges61 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

SCaffrey · Accepted Answer · 2016-03-06 01:16:14Z

1

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;
}

answered Mar 6, 2016 at 1:16

SCaffrey

3511 gold badge3 silver badges14 bronze badges

2 Comments

jpro Over a year ago

Thank you so much for your answer! And with the way you changed the for loop is not necessary to check for an overflow right?

SCaffrey Over a year ago

Using long with the for loop might help. I guess that the module result * 37 might still overflow if the tableSize is big enough. BTW, the answer by @Artem describes the reason why integers are overflowing.

Collectives™ on Stack Overflow

Hash Function Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related