c++ - 多项式哈希码结果为负数？

Question

在某些情况下对于大 j 函数，下面的哈希函数返回负值。

int hashing::hash(string a)
{
    int i = 0;
    int hvalue = 0;
    int h =0 ;
    while(a[i]!=NULL)
    {
        hvalue = hvalue + (int(a[i]))*pow(31,i);
        i++;
    }
    h = hvalue%j;
    return h;
}

这怎么可能？我该如何纠正它？

在上面的代码中，j 是使用文件大小计算的质数。负值出现在某些特定情况下，其中字符串的形式为“the s”。

我做错了什么？我该如何解决？

Answer 1

记住 int有一个有限的范围，并且(通常)是一个有符号的值。这意味着如果您超过 int 的最大可能值, 它会环绕并可能变为负值。

有几种方法可以解决这个问题。首先，您可以切换到使用 unsigned int s 保存哈希码，它永远不会是负数，并且在回绕时会表现得很好。或者，如果您仍想使用 int s，您可以通过执行以下操作来屏蔽符号位(数字前面使值变为负数的位):

return (hvalue & INT_MAX) % j;

(此处，INT_MAX 在 <climits> 中定义)。这将确保您的值是正的，尽管您从哈希码中丢失了一点，这对于大型数据集可能会导致更多的聚类。做 & 的原因在 mod 之前，您要确保在采用 mod 之前该值为正，否则您将溢出桶的数量。

编辑:您的逻辑也有严重错误。这个循环是不正确的:

while(a[i]!=NULL) {
    ...
}

C++ 风格的字符串不是以 null 结尾的，因此不能保证一旦您读到字符串末尾就会停止。尝试将其更改为阅读

for (int i = 0; i < a.length(); i++) { 
    /* ... process a[i] ... */
}

希望这对您有所帮助!