c++ - 散列溢出

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是否小于零？这怎么可能？

最佳答案

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

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

可能导致hashVal的值超过int的最大值（通常为231 − 1），并变为负数。这称为integer overflow。

C ++标准does not specify负操作数的%运算符的值应为正还是为负；因此，根据您的编译器和CPU体系结构（以及可能的编译时开关），类似-47 % 37的表达式的结果可能为-10或27。因此，您引用的代码通过在结果为负数时将模数添加到结果中来防止前一种可能性。

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