31

​Здравствуйте.

Мне нужна помощь математика. Меня зовут Кирилл, я ​программист.

Существует такая вещь, как хэш-функция. ​Это функция, которую можно использовать для отображения данных произвольного размера на данные фиксированного размера.

Фиксированный размер обычно находится в диапазоне от -2147483648 до 2147483647 (всего 32 бита). Это позволяет выполнять быстрый поиск.

Итак, нам нужна наша хеш-функция:

   с​тойкая (которая возвращает одинаковый результат для одного агрумента)

   лучшее распределение значений, которое мы можем получить (чтобы избежать ​коллизий)

Так что мой вопрос о ​втором. Во многих языках программирования хеш-функция вычисляется с использованием числа 31.

Если P0, P1 ... Pn - свойства объекта, представленные в виде чисел, а H - значение хеш-кода, то:

H = P0

H = H * 31 + P1

​​.

.

.​

H = H * 31 + Pn

возвращаем H

Интересно, почему используют 31. Очевидно, потому что это дает лучшее распределение. ​Говорят, ​причина в том, что это​ во-первых​ простое число и​ во-вторых​ его удобно вычислять:

х * 31 = х << 5 - 1

Где << - двоичн​ый​ лев​ый​ ​сдвиг. Это две примитивные операции, которые можно очень быстро выполнить на процессоре. Нам нужно использовать нечетное число, потому что умножение на четное число всегда стирает последний бит, что ​уменьшает распределение вдвое.

Но почему не 7 или 17 тогда? Почему не 127?

х * 7 = х << 3 - 1

х * 17 = х << 4 + 1

х * 127 = х << 6 - 1

Почему простые числа вообще?

Опять же, с прагматической точки зрения ответ очевиден - экспериментально доказано, что распределение лучше. Оно вообще лучше у простых чисел, а у 31 лучше всех.

Но почему? Есть ли способ рассуждать об этом, не анализируя экспериментально полученные распределения? Есть ли способ сравнить хотя бы эти числа по эффективности, кроме статистических аргументов?​ Буду благодарен любой помощи или подсказке.​

С наилучшими пожеланиями,

Кирилл