-2

In the code given, it was trying to give a valid index for a hashtable by checking for any collision using another method linearprobe. I am just confuse of why we need to check for index < 0, so will there be instance when hashCode will be negative? When/why will that happens?

private int getHashIndex(K key)
{
   //1.convert key to hashcode, then get the index;
  //2. then use linear probing to check for the correct index;
  int index = key.hashCode() % hashTable.length; 
  if(index < 0) { //So a hash code can be negative?
    index += hashTable.length;
  }

  index = linearProbe(index,key);

  return index;

}
Jenna Tokoshi
  • 7
  • 1

1 Answers1

1

Yes, If the string given is long enough, then its hashcode will be greater than largest integer that can be stored on 32 bits CPU. So in this case, due to integer overflow, the value returned by hashCode can be negative.

ref : https://www.cs.cmu.edu/~adamchik/15-121/lectures/Hashing/hashing.html

Hope its helps !

Shubham
  • 549
  • 4
  • 11
  • Depending on the hash function, "long enough" can be two or three characters. – Jim Mischel Dec 10 '19 at 18:31
  • 1
    There are other objects than strings. E.g. it’s easy to predict the negative hashode of `Integer.valueOf(-1).hashCode()`… – Holger Jan 17 '20 at 14:35