java - 哈希为负值

Question

与标题差不多:我正在对一堆名称(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;
}

我仔细研究了一下，我想我必须做一些与“环绕”有关的事情。但我不知道该怎么做。

Answer 1

这是一个明显的整数溢出案例。正如您在问题中提到的，字符串最多可以有 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;
}