Какое наибольшее подходящее целое число для хождения по модулю?
Учитывая алгоритм, который использует хеш-функцию по модулю, то есть большие числа, превышающие определенное заданное целое число, будут "оборачиваться", поэтому результат всегда будет между 0 и заданным целым числом. Например, алгоритм Рабина-Карпа нуждается в скользящем хеше с умным модулем. Какое самое высокое по модулю возможно? И почему так?
1 ответ
Чтобы ответить на этот вопрос, важно проверить, какая операция с наибольшим эффектом происходит между вызовами по модулю. Это означает, что если вы ожидаете, что число будет оптимально умножено на 97*101=9797, вы должны поделить 2^(32) на 9797 (из примера Рабина-Карпа), а затем искать ближайшее простое число в этой области. Например, если вы добавите 2600 к целому числу, вы должны вычесть 2600 из 2^(32). Если вы поставите квадрат в квадрат, то вам нужно взять квадратный корень из 2^(32) и т. Д.
Это предотвратит переполнение после операции и до вызова по модулю. Поэтому всегда сохраняйте хешированное число между 0 и выбранным простым числом.
Поскольку вы выбрали (высокое) простое число, число коллизий хешей будет как можно меньше.