1

对于较大的 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 是使用文件大小计算的素数。负值出现在字符串具有“s”形式的某些特定情况下。

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

4

1 回答 1

1

请记住，它int具有有限范围并且（通常）是有符号值。这意味着，如果您超过 a 的最大可能值int，它将环绕并可能变为负数。

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

return (hvalue & INT_MAX) % j;

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

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

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

C++ 风格的字符串不是以空值结尾的，所以一旦你读到字符串的末尾，就不能保证停止。尝试将其更改为阅读

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

希望这可以帮助！

于 2013-10-25T22:53:14.800 回答