0 
int hash (const string &key, int tableSize) {
   int hashVal = 0; 

   for (int i = 0; i < key.length(); i++)
        hashVal = 37*hashVal + key[i]; 
   hashVal %= tableSize; 
   if (hashVal < 0)   /* in case overflows occurs */
        hashVal += tableSize; 

   return hashVal;      
};

为什么我们要控制 hashVal 是否小于零？这怎么可能？

4

5 回答 5

2

您可以在变量 hashVal 中溢出。这（有时）会导致负值。例如，尝试在 C++ 程序中打印 3 * 1000 * 1000 * 1000 的值：

std::cout << 3 * 1000 * 1000 * 1000;

在我的计算机上，使用我的编译器，它会打印 -1294967296。

结果 3000000000 是二进制的 10110010110100000101111000000000，但由于在这个特定平台上整数是 32 位，并且我们使用二进制补码方法来表示负数，所以这个位模式表示负数。

该标准将整数溢出定义为未定义的行为，因此实际上任何事情都可能发生，但这是典型的效果。

于 2012-12-30T12:34:22.267 回答
2

如果字符串足够长，代码：

for (int i = 0; i < key.length(); i++)
    hashVal = 37*hashVal + key[i];

可能会导致 的值hashVal超过 an 的最大值int（通常类似于 2 31 - 1）并变为负数。这称为整数溢出。

C++ 标准没有规定负操作数的操作符的值%是正数还是负数；因此，根据您的编译器和 CPU 架构（以及可能的编译时开关），表达式 like-47 % 37可能会计算为-10or 或27. 因此，您引用的代码通过在结果为负数时将模数添加到结果中来防止前一种可能性。

顺便说一句，避免此问题的更简单方法是将定义hashVal为无符号。

于 2012-12-30T12:38:27.177 回答
0

如果 key 足够长，hashValvalue 可能会变为负数。您可以尝试不同长度的字符串（例如“1”、“11”、“111”、“1111”等），看看哪里hashVal会变成负数（大约 5-7 个字符就足够了）。

然后你尝试得到负数的模，这也是负数。但是您不能指向负数组索引（似乎，此函数计算要存储的字符串的位置），因此您将其设为正并且适合作为数组索引。

于 2012-12-30T12:38:37.353 回答
0

hashVal在for循环中变得越来越大，它很容易变得大于signed int最大值，这取决于平台。如果hashVal在for循环之后为负，则在操作符之后可能仍然为负%=，这也是平台相关的（在某些情况下，它总是返回非负值，而它也可能返回负值）然后，您需要在hashVal之后检查是否为负。

于 2012-12-30T12:41:03.417 回答
0

尝试通过以下方式调用您的哈希函数

hash("HelloHello",100);

然后单步执行程序或在散列函数中打印一条消息，以查看散列是否低于 0。

例如，在for循环中你可以放

if(hashVal < 0)
{
    cout<<"OVERFLOW HAS HAPPENED\n";
    break;
}

你会看到 hashVal 低于 0。

于 2012-12-30T12:45:58.220 回答