Java - int НЕ БУДЕТ переполняться хешированием
Итак, я только начинаю изучать объектно-ориентированное программирование на Java, и мне нужно сделать этот хешированный словарь. Я должен хешировать имя с помощью алгоритма и возвращать хэшированное значение. Лаборатория сказала сделать
int n = s.length();
for (int i = 0; i < n; i++)
hash = g * hash + s.charAt(i);
где g = 31, s = имя + фамилия;
и я посмотрел на это и поместил его в код. То, что я написал, было
public int hashCode() // part of the Name class
{
int h = 0;
String bothNames = first + last;
for (int i = 0; i < bothNames.length(); i++) {
h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1);
}
return h;
}
Теперь, когда я запустил этот код для чего-то вроде Name testName = new Name("Wayne", "Gretzky"); и распечатал testName.hashCode(), я почти всегда возвращал ограничение на 32-битное целое, что означало, что он не переполнялся. Однако, когда я изменил цикл for на
for (int i = 0; i < bothNames.length(); i++) {
h = g*h + bothNames.charAt(i);
}
вдруг снова переполнился. Я не очень понимаю, почему это могло произойти. Две хеш-функции должны быть одинаковыми. Почему h не переполняется в первом случае? Заранее спасибо.
Ну, исходная хеш-функция была h = u_0 g^(n - 1) + u_1 g^(n - 2) + … + u_(n - 2) g + u_(n - 1), и обе они должны выполнять то же самое, вы получаете термины один за другим, который был моим первоначальным, а новый делает это немного по-другому. Я работал с ними обоими, и похоже, что они должны быть одинаковыми, u_k * g^(n-k) — это терм в обеих хеш-функциях.
Ответы 2
Проблема в следующем:
h += bothNames.charAt(i)*Math.pow(g, bothNames.length() - i-1)
Метод pow возвращает большое значение double. Который вы умножаете на целое число, чтобы получить большее значение double. Затем h += ... выполняет преобразование примитивное сужение из double в int.
Преобразование double в int — это определенный для преобразования любого значения с плавающей запятой, превышающего Integer.MAX_VALUE, в Integer.MAX_VALUE (!).
Решением будет вычисление gk с помощью целочисленной арифметики; например используя повторение:
g0 = 1
gk = g * gk - 1 (for k > 0).
Давайте посмотрим на следующую строку:
h += bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1);
Учитывая природу составные операторы присваивания, это эквивалентно:
h = (int)(h + (bothNames.charAt(i) * Math.pow(g, bothNames.length() - i - 1)));
Все бы ничего, если бы не тот факт, что Math.pow возвращает double. Принимая во внимание регулярные правила расширения:
h = (int)(intValue + (intValue * doubleValue))
h = (int)(intValue + doubleValue)
h = (int)(doubleValue)
Последнее doubleValue сужается до int. Если строка достаточно длинная, doubleValue превысит Integer.MAX_VALUE с первой итерации.
«Две хэш-функции должны быть одинаковыми». Как вы это понимаете?