哈希值为负值

非常多标题：我哈希了一堆名称（10000-ish），有些输出为负值。（表格大小是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; 
}

我周围挖，我想我要做的是与“环绕”。但我不知道如何去做。

来源

2017-05-09 Alex M

如果您不确定它是否“环绕”，请使用“Math.toIntExact”。如果是这种情况，这应该会引发异常。另外，考虑到你的方法返回类型是'long'，为什么不声明'hashVal'长？ –

当你定义'hash2（）'返回'long'时，为什么你要用'int'来表示'hashVal'？同样使用“长”。 –

这是一个明确的案例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; 
}

来源

2017-05-09 12:24:38

hashVal是一个整数。这很可能是你的散列函数导致整数溢出。

您可以使用Math.abs()轻松解决此问题，以确保hashVal是一个正数。例如

hashVal = hashVal == Integer.MIN_VALUE ? 0 : Math.abs(hashVal); 
return hashVal % 20011;

国防部%是确保计算的最终索引是表的范围内（即，如果它是> = 20011，它采用分割为你说的其余“环绕”）。

来源

2017-05-09 12:25:16

请注意'Math.abs（Integer.MIN_VALUE）'返回'Integer.MIN_VALUE'。 –

虽然我不确定它是如何影响分布的，但可以修改为'Math.abs（hashVal％20011）'。 –

@StefanWarminski更新以反映这种特殊情况。 –

哈希值为负值

回答

相关问题