Справка с помощью правила Horner's и хеш-функций в Java?
Я пытаюсь использовать правило Horner's преобразовать слова в целые числа. Я понимаю, как это работает и как, если слово долго, оно может вызвать переполнение. Моя конечная цель должна использовать преобразованное целое число в хеш-функции h (x) =x модификация tableSize. Моя книга предлагает из-за переполнения, Вы могли "применить оператор Mod после вычислений каждого заключенного в скобки выражения в правиле Horner's". Я точно не понимаю то, что они подразумевают под этим. Скажите, что выражение похоже на это:
((14*32+15) *32+20) *32+5
Я беру модификацию tableSize после каждого заключенного в скобки выражения и добавляю их вместе? На что это было бы похоже с этой хеш-функцией и этим примером правила Horner's?
2 ответа
Они имеют в виду замену результата выражения с круглыми скобками на этот результат mod tableSize:
((((14*32+15)%tableSize)*32+20)%tableSize)*32+5
В книге говорится, что вы должны воспользоваться преимуществами этих математических эквивалентностей:
(a * b) mod m = ((a mod m) * (b mod m)) mod m
(a + b) mod m = ((a mod m) + (b mod m)) mod m
Таким образом,
h = (((x*c) + y)*c + z) mod m
эквивалентно
_ _ _ _
h = (((x*c) + y)*c + z)
Где
_
a * b = ((a mod m) * (b mod m)) mod m
_
a + b = ((a mod m) + (b mod m)) mod m
По сути, для каждого базового сложения и базового вычитания вы заменяете его «расширенной» версией, которая модифицирует операнды, а модифицирует результаты. Поскольку операнды базового умножения теперь находятся в диапазоне 0..m-1 , наибольшее число, которое вы получите, будет (m-1) ^ 2 , что может облегчить переполнение, если м достаточно мало.
См. Также
- Википедия: модульное возведение в степень
- Википедия: операция по модулю
-1 mod 2 = 1математически, но-1% 2в Java - это-1.
Кстати, следует отметить, что 32 - ужасный выбор множителя для хэш-функций этого класса (поскольку это не простое число), особенно для вычислений (поскольку это степень двойки). Намного лучше 31, потому что:
- Это простое число (математически важно!)
- Оно на единицу меньше степени двойки, поэтому его можно оптимизировать до более дешевого сдвига и вычесть
31 * i == (i << 5) - i