Примеры хеш-функций. Методы построения хеш-функций для целых чисел

Тимофей: Выбор хеш-функций зависит от задачи.

Вернёмся к примеру, в котором в качестве хеш-функции мы брали индекс первой буквы товара, равный её порядковому номеру в алфавите. Например, для «арбуз» функция вернула бы 1, для «банан» — 2, а для «яблоко» — 33.

Есть ли у этой функции недостатки?

Нет. Эту хеш-функцию можно применять для любой задачи.

Вычислить такую функцию можно очень быстро. Но при её использовании в таблице будет всего 33 ячейки. Будут возникать коллизии. К тому же распределение по ячейкам будет неравномерным.

Есть задачи, для которых эта хеш-функция не подойдёт. Но для примера с магазином она в самый раз.

Недостаток в том, что функция будет возвращать не больше 33 значений. Значит, может быть много коллизий.

Распределение данных по ключам будет неравномерным. Например, на букву «а» будет много товаров, а на «ъ» и «ы» — вообще не будет.

Функция будет вычисляться достаточно долго.

Гоша: Можно в качестве хеш-функции использовать остаток от деления последних трёх цифр цены на 1000.

Есть ли у этой функции недостатки?

На этот раз функция хорошая и её можно использовать для данной задачи. Ведь цены на товары очень разные. Коллизии не будут возникать часто.

Цены многих товаров оканчиваются на 000, 500, 999, 900. Это приведёт к тому, что коллизии будут возникать довольно часто. Скоро вы узнаете, почему это плохо.

При использовании этой функции будут часто возникать коллизии.

Тимофей: Выбор хеш-функции должен зависеть от данных, с которыми вы работаете. Допустим, вы работаете с целыми числами. Тогда можно воспользоваться методом деления.

Метод деления

В случае работы с целыми числами самый простой вариант — брать остаток от деления.

h(k) = k \bmod M

, где

M

определяет диапазон значений

[0, M-1]

. То есть от этого числа будем считать остаток от деления.

k

— аргумент, от которого хотим вычислить значение хеш-функции

h(k)

Тимофей: Значение

M

нужно подбирать с учётом специфики задачи и имеющихся ресурсов. Если параметр будет слишком мал, возникнет много коллизий. Если слишком большой, потребуется много памяти для хранения таблицы.

Алла: А как именно выбрать

M

Гоша: Можно взять в качестве

M

степень двойки. В программировании часто используют константы такого вида.

То есть

M = 2^p

для некоторого числа

p

Тимофей: Это неудачный выбор. В этом случае функция

h(k)

— просто набор младших битов числа

k

. То есть значение не зависит от старших байтов.

Гоша: Почему не зависит? Можешь привести пример?

Возьмём

M = 2^4

Переведём это число в двоичную систему счисления.

M = 2^4 = 16 = 10000.

Посчитаем значение

h(k)

для некоторых

k

Например, для

k = 5

. Переведём число

k

в двоичную систему и посчитаем остаток от деления на

M

Гоша: А как считать остаток от деления одного числа на другое, если они представлены в двоичной системе счисления?

Тимофей: Деление чисел в двоичной системе счисления производится по тем же правилам, что и для десятичных чисел. Даже ещё проще, поскольку мы имеем всегда только две цифры — 0 и 1.

h(5) = h(0101) = 5

h(21) = h(10101) = 5

h(37) = h(100101) = 5

h(53) = h(110101) = 5

h(69) = h(1000101) = 5

Гоша: Да, действительно. Функция выдаёт одинаковый ответ для разных

k

. Будут возникать коллизии. А зачем нужно было переводить числа в двоичную систему? Разве так нельзя было посчитать остаток от деления?

Тимофей: Можно. Мы перевели числа в двоичную систему, чтобы лучше понять утверждение про младшие биты.

Алла: Как же тогда подобрать

M

Тимофей: В качестве

M

нужно брать простое число.

Гоша: Напомни, что такое простое число?

Рита: Простое число — это число, которое делится без остатка только на себя и на 1.

Гоша: А, точно. Я знал, просто забыл.

Алла: А почему нужно брать простое число?

Тимофей: Рассмотрим пример. Пусть имеется хеш-таблица размером 12, и есть набор ключей

[0, 1, ..., 100]

Так как 3 — делитель 12, ключи, которые делятся на 3, попадут в ячейки, номера которых тоже делятся на 3.

[0, 12, 24, 36, ...]

попадут в ячейку с номером 0.

[3, 15, 27, 39, ...]

— в ячейку с номером 3.

[6, 18, 30, 42, ...]

— в ячейку с номером 6.

[9, 21, 33, 45, ...]

— в ячейку с номером 9.

Чтобы избежать коллизий, нужно уменьшить число общих делителей

M

и элементами множества ключей. В этом поможет выбор простого числа в качестве размера таблицы.

Тимофей: Хороший результат получается, если в качестве

M

выбирать простое число, далеко отстоящее от степеней двойки.

Например, при наличии 2000 элементов в качестве

M

можно взять число 701. Оно простое и примерно на равном расстоянии отстоит от чисел, являющихся степенями двойки

(512 = 2^9 < 701 < 2^{10} = 1024)

. При таком выборе

M

с высокой вероятностью количество элементов, для которых значение хеш-функции совпадёт, будет в среднем равно

3 \displaystyle \left ( \frac{2000}{701} \approx 2,85 \right)

Реализуем код хеш-функции, которая для определения индекса элемента берёт остаток от деления на 17.

Скопировать кодJSX
def hashFunction(key)
{
  return key % 17
}

Гоша: А что обозначает знак

\%

Тимофей: Это остаток от деления по модулю 17. Например, если на вход функции подать число 19, то остаток будет 2. Если 15, то остаток будет 15. Можно просто говорить «15 по модулю 17».

Что получится, если на вход функции подать 34?

Чему равно 42 по модулю 5?

Гоша: Не знал, что так просто можно реализовать хеш-функцию. Интересный метод. Взятие остатка от деления — единственный приём, который используется при работе с целыми числами?

Тимофей: Нет. Есть и другие методы.

Метод умножения

Тимофей: Это ещё один популярный способ, применяемый для вычисления хеша при работе с целыми числами.

Пусть количество возможных хеш-значений равно

M

и есть константа

A \in (0,1)

. Тогда

h(k) = \left [ M \cdot \left \{ k \cdot A \right \} \right ]

, где

\left [ x \right ]

— это целая часть числа

x

\left \{ x \right \}

— его дробная часть.

A

— некоторое число от 0 до 1. То есть

0 < A < 1

M

определяет диапазон значений

[0,..., M-1]

k

— ключ.

Алгоритм построения хеш-функции с использованием метода умножения:

Домножаем $k$ на $A$ .
Берём от результата дробную часть. Получается некоторое значение от 0 до 1. Важно, что значения для разных ключей будут равномерно рассеяны в диапазоне от 0 до 1. В конечном итоге мы хотим избежать коллизий.
Домножаем его на размер таблицы $M$ .
Берём от полученного значения целую часть. Получаем число, равномерно рассеянное в диапазоне от $0$ до $M - 1$ . То есть таблица будут заполнена равномерно.

Алла: Здорово, очень интересный метод.

Гоша: Как подобрать

M

мы знаем. Осталось узнать, как выбрать

A

Тимофей: Дональд Кнут провёл исследования и выяснил, что хеш-функция получается хорошей, если в качестве

A

брать число, обратное золотому сечению.

\displaystyle A = \phi^{-1} = \left ( \frac{\sqrt 5 -1}{2} \right ) = 0.6180339887...

Алла: А почему так?

Тимофей: Это значение было получено экспериментально.

Есть ли недостатки в этом алгоритме?

Недостатков нет. Наконец-то нашли способ борьбы с коллизиями.

Эта функция не эффективна, так как нужно вычислять

\sqrt 5

Эта функция не эффективна. Работа с числами с плавающей точкой, чем и является дробная часть, очень дорогая операция. Перемножить два числа с плавающей точкой для компьютера почти на порядок сложнее, чем два целых числа.

Хотелось бы как-то обойтись без этого. Важно, чтобы хеш-функция вычислялась быстро.

Возьмём

M = 2^p

, где

p

— некоторое простое число,

p \leqslant 32

Алла: Ты же говорил, что брать степень двойки — не лучший вариант.

Тимофей: Так было в случае взятия остатка от деления. В этом методе такой проблемы не будет.

Вместо действительного числа А можно взять близкое к нему

A = \displaystyle \frac{S}{2^{32}}

То есть

S = 2654435769

— целое число.

Разобьём число

k\cdot S

на два слагаемых: число, которое больше, чем

2 ^{32}

и число, которое меньше, чем

2 ^{32}

. То есть представим его в виде

r_1 \cdot 2^{32} + r_0

h(k) = \left [ M \cdot \left \{ k \cdot A \right \} \right ]= \left [ 2^p \cdot \left \{ k \cdot \displaystyle \frac{S}{2^{32}} \right \} \right ] = \left [ 2^p \cdot \displaystyle \frac{r_1 \cdot 2^{32} + r_0}{2^{32}} \right ].

Так как нам интересна дробная часть от второго остатка

\displaystyle \frac{r_0}{2^{32}},

то

\left [ 2^p \cdot \displaystyle \frac{r_0}{2^{32}} \right ] = \left [ \displaystyle \frac{r_0}{2^{32-p}} \right ]

Аналогично разобьём

r_0

на два слагаемых: больше, чем

2^{32-p}

и меньше.

\displaystyle \left[\frac{r_{01} \cdot 2^{32-p}+r_{00}}{2^{32-p}}\right]

Теперь нас интересует только целая часть, то есть получаем

r_{01}

Получим, что

h(k)=\left(k \cdot s \bmod 2^{32}\right) \gg(32-p)

Рита: Действительно, получилось избавиться от необходимости использования чисел с плавающей точкой.

Алла: Я не очень поняла последние два перехода. И что это за значок, похожий на двойное «больше»?

Тимофей: Давай по порядку. Знак ">>" — побитовой сдвиг вправо. Также можно делать побитовой сдвиг влево. Он обозначается символом "<<".

Пусть у нас есть число 10101010. Посмотрим, что получится при сдвиге на 1 бит влево, и вправо:

Если сделать сдвиг влево на 1 бит, получим число 01010100.
Если сделать сдвиг исходного числа вправо на 1 бит, получим число 01010101.

Что получится, если вычислить операцию побитового сдвига влево на 1 бит для числа 6?

Переведём 6 в двоичную систему. Получим 110. Произведём операцию побитового сдвига влево на 1. Результатом будет 1100, то есть 12.

Что получится, если вычислить операцию побитового сдвига вправо на 2 бита для числа 88?

Переведём 88 в двоичную систему. Получим 1011000. Произведём операцию побитового сдвига вправо на 2. Результатом будет 10110, то есть 22.

325

Побитовый сдвиг влево на один соответствует умножению на два, вправо — делению на два.

Тимофей: Теперь разберёмся, как получились два последних перехода в формулах.

h(k)=\left(k \cdot s \bmod 2^{32}\right) \gg(32-p)

r_0

— остаток от деления

k \cdot s

на

2^{32}

. Делим это число на

2^{32-p}

, что равносильно побитовому сдвигу вправо на

32-p

. Ведь если сдвиг на 1 — то же самое, что разделить на 2, то если сдвинем

32-p

раз, получим то же самое, как если бы мы разделили на

2^{32-p}

. Теперь понятно, как получился ответ?

Алла: Теперь да, спасибо.

Решите задачу P: https://contest.yandex.ru/contest/19095/problems/P