Что такое хэш-таблица?

Это способ создать ассоциативный массив, который бы работал так же быстро, как обычный массив.

Почему обычный массив быстро работает?

Потому что для размещения элементов используется нумерация от 0 до N-1 (где N - количество элементов в массиве), поэтому для вычисления адреса памяти для доступа к элементу достаточно умножить индекс на размер элемента и прибавить к начальному адресу массива.

Почему нельзя точно также создать ассоциативный массив?

Потому что залогом эффективности массива является индексирование всех элементов целыми числами от 0 до N-1. В ассоциативном же массиве ключами могут быть экземпляры любого объекта, которые нельзя однозначно переводить в целые числа от 0 до N-1.

И в этом нам поможет хэширование?

Да, именно так, Функция хэширования выдаёт конкретное целое число от 0 до N-1 для любого экземпляра любого объекта.

Как можно получить целое число из экземпляра любого объекта?

Для этого в классе object есть метод getHashCode(), задача которого конвертировать любой экземпляр объекта в целое 32-битное число от -maxint до +maxint. При создании пользовательского класса для ключей, следует озаботиться переопределением этого метода и составлением хорошей формулы для вычисления хэш-кода. Это должна быть “чистая функция”: для одинаковых экземпляров необходимо выдавать одинаковые числа, а для разных - разные.

А понял! А потом нужно найти остаток от деления на N, да?

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

Math.Abs(K.GetHashCode() % N)

А хватит ли N чисел для всех возможных вариантов ключей?

Нет, конечно. Множество возможных вариантов экземпляров ключей - число очень большое, непредсказуемое! Например, существует больше триллиона (256^5) значений для всех вариантов строчек из пяти ASCII символов. Во время хэширования мы можем получать одинаковые значения для совершенно разных ключей как на этапе вычисления функции getHashCode(реже), так и на этапе нахождения остатка (чаще). Эти совпадения называются коллизиями.

Можно привести пример коллизий из реальной жизни?

Например, если “хэшировать” людей по росту в миллиметрах, то будет возникать коллизии на первом этапе хэширования для людей одинакового возраста. 

А если, например, записывать режим дня на циферблате, то события в 6 и в 18 часов окажутся в одном месте. Это коллизия на этапе нахождения остатка. 

Как разрешать коллизии?

Есть разные способы, например “метод цепочек”, “метод открытой адресации”, “метод двойного хэширования”. Каждый способ определяет правило размещения и поиска элементов с одинаковыми хэш-значениями.

Можно поподробнее о методе цепочек?

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

А как мы сможем найти в этом списке элемент по ключу?

Для этого придётся хранить значение ключа. В обыкновенном массиве коллизий не бывает, каждый элемент имеет свой уникальный индекс от 0 до N-1, поэтому нет необходимости дополнительно хранить сам индекс. А в хэш-таблице мы обязаны в каждом элементе хранить не только значение, но и сам ключ, чтобы во время перебора элементов с одинаковыми хэш-значениями мы смогли однозначно найти нужный, либо рапортовать, что ключ не найден. Получаются накладные расходы на хранения всех ключей.

Можно перечислить все действия для добавления элемента в хэш-таблицу?

• Первое. Вычислить хэш-код ключа, получим число int32

• Второе. Найти остаток от деления на размер таблицы N - получим индекс.

• Третье. Пройти по односвязному списку, чтобы убедиться, что такого ключа ещё нет.

• Четвёртое. Разместить новый элемент в начало односвязного списка.

Вот карта сокровищ хэширования:

А всем места хватит?

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

А можно увеличить размер хэш-таблицы?

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

Как интересно. Можно узнать про другие алгоритмы?

Конечно, записывайтесь на курс “Алгоритмы и структуры данных” в Отус. Онлайн образование, мы там на вебинарах рассматриваем очень много разных алгоритмов, не только про хэширование, но и про двоичные деревья поиска, теорию графов, способы сжатия данных и шифрования, и многое другое.