Переполнение хеширования
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) и стать отрицательным. Это известно как целочисленное переполнение.
Стандарт C ++ не указывает является ли значение % оператор для отрицательных операндов должен быть положительным или отрицательным; таким образом, в зависимости от вашего компилятора и архитектуры процессора (и, возможно, переключателей во время компиляции), выражение как -47 % 37 может оценить либо -10 или же 27, Таким образом, код, который вы цитировали, защищает от первой возможности, добавляя модуль к результату, если он отрицательный.
Кстати, проще было бы избежать этой проблемы, чтобы определить hashVal как без знака.
Другие решения
Вы можете получить переполнение в переменной hashVal. Это (иногда) приводит к отрицательному значению. Например, попробуйте напечатать значение 3 * 1000 * 1000 * 1000 в программе на C ++:
std::cout << 3 * 1000 * 1000 * 1000;
На моем компьютере и с моим компилятором это печатает -1294967296.
В результате получается, что результат 3000000000 равен 10110010110100000101111000000000 в двоичном формате, но поскольку целые числа являются 32-разрядными на этой конкретной платформе, и мы используем метод двойного дополнения для представления отрицательных чисел, этот битовый шаблон представляет отрицательное число.
Стандарт определяет целочисленное переполнение как неопределенное поведение, поэтому на самом деле может произойти все что угодно, но это типичный эффект.
Если ключ достаточно длинный, hashVal значение может стать отрицательным. Вы можете поэкспериментировать со строками разной длины (например, «1», «11», «111», «1111» и т. Д.), Чтобы увидеть, где hashVal станет отрицательным (около 5-7 символов должно быть достаточно).
Затем вы пытаетесь получить по модулю отрицательное число, которое также будет отрицательным. Но вы не можете указывать на отрицательный индекс массива (кажется, эта функция вычисляет позицию для строки, в которой будет храниться), поэтому вы делаете ее положительной и подходящей для индекса массива.
hashVal становится все больше и больше очень быстро в for петля, она может легко стать больше, чем самая большая signed int значение, которое зависит от платформы.
Если hashVal были отрицательными после for цикл, он все еще может быть отрицательным после %= оператор, который также зависит от платформы (в некоторых случаях он всегда возвращает отрицательные значения, в то время как он также может возвращать отрицательные значения), тогда вам необходимо проверить, hashVal отрицательный впоследствии.
Попробуйте вызвать вашу хэш-функцию следующим образом
hash("HelloHello",100);
А затем пошагово пройдитесь по программе или распечатайте сообщение в хэш-функции, чтобы увидеть, опустится ли когда-нибудь хэш ниже 0
Например, в for петлю можно поставить
if(hashVal < 0)
{
cout<<"OVERFLOW HAS HAPPENED\n";
break;
}
И вы увидите, что hashVal будет ниже 0.