哈希溢出

Question

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是否小于0 ?这怎么可能呢?

Answer 1

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

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

可能导致hashVal的值超过int的最大值(通常是2³¹ & -;1)变得消极。这被称为整数溢出。

c++标准没有规定负操作数的%操作符的值应该是正的还是负的;因此，取决于您的编译器和CPU体系结构(可能还有编译时开关)，像-47 % 37这样的表达式可能求值为-10或27。因此，您所引用的代码通过在结果为负时添加模数来防止前一种可能性。

顺便说一下，避免这个问题的一个更简单的方法是将hashVal定义为unsigned

Answer 2

您可以在变量hashVal中获得溢出。这(有时)会导致负值。例如，尝试在c++程序中打印3 * 1000 * 1000 * 1000的值:

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

在我的计算机上，在我的编译器中，打印-1294967296。

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

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

Answer 3

如果key足够长，hashVal值可能变为负值。你可以尝试不同长度的字符串(例如"1"，"11"，"111"，"1111"等)，看看hashVal在哪里会变成负的(大约5-7个字符应该足够了)。

然后求负数的模，结果也是负的。但是你不能指向负的数组索引(看起来，这个函数计算要存储的字符串的位置)，所以你把它设置为正的，适合作为数组索引。

Answer 4

hashVal在for循环中变得越来越大，它很容易比signed int的最大值更大，这与平台有关。如果hashVal在for循环之后是负的，那么在%=操作符之后可能仍然是负的，这也是平台相关的(在某些情况下，它总是返回非负的值，同时也可能返回负的值)，那么您需要检查hashVal之后是否为负。

Answer 5

试试用下面的方法调用哈希函数

hash("HelloHello",100);

然后遍历程序或在哈希函数中打印一条消息，以查看哈希值是否低于0。

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

if(hashVal < 0)
{
    cout<<"OVERFLOW HAS HAPPENEDn";
    break;
}

你会看到hashVal小于0