java - 散列为负值

标题差不多：我正在散列一堆名称（10000位数），有些输出为负数。 （表格大小为20011）。

有问题的哈希函数是：

public static long hash2 ( String key ){
  int hashVal = 0;
    for( int i = 0; i < key.length(); i++ )
      hashVal = (37 * hashVal) + key.charAt(i);
  return hashVal % 20011;
}

我挖了周围，我想我必须做些“环绕”的事情。但是我不知道该怎么做。

最佳答案

这是Integer Overflow的明显情况。正如您在问题中提到的那样，字符串最多可以包含10000个字符，因此hashValue肯定会溢出，因为需要在37^10000周围存储值。即使这将失败，长度为20的字符串。

在数论中

(A+B)%M = (A%M + B%M) % M;
(A*B)%M = (A%M * B%M) % M;

您应该在for循环中应用模运算。但是，如果最后执行模运算或在for循环中执行模运算，则如果不发生溢出，两者将给出相同的答案。

因此进行相应的更改，

public static long hash2 ( String key ){
  int hashVal = 0;
    for( int i = 0; i < key.length(); i++ )
    {
      hashVal = (37 * hashVal) + key.charAt(i);
      hashVal%=20011;
    }
  return hashVal;
}