Хеш-таблицы и хеширование

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

Хеш-таблица — это структура данных, которая хранит пары «ключ — значение» и позволяет очень быстро находить значение по ключу. В основе лежит хеш-функция — правило, которое по ключу вычисляет число (индекс) ячейки массива, где хранят данные.

Благодаря этому поиск, добавление и удаление в среднем выполняются за постоянное время, не зависящее от числа элементов. Это намного быстрее, чем перебор всего массива.

Как работает хеш-функция

Хеш-функция превращает ключ (число, строку) в индекс в пределах размера таблицы. Например, для целого ключа простейшая функция — остаток от деления на размер таблицы:

индекс = ключ mod размер_таблицы

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

Коллизии

Коллизия — это ситуация, когда два разных ключа дают один и тот же индекс. Коллизии неизбежны, и их нужно разрешать. Два основных способа:

• метод цепочек — в каждой ячейке хранят список всех элементов с этим индексом;
• открытая адресация — при занятой ячейке ищут следующую свободную.

Операция	В среднем	В худшем случае
Поиск	постоянное время	линейное
Добавление	постоянное время	линейное
Удаление	постоянное время	линейное

Разбор примера

Поместим ключи 5, 12 и 22 в таблицу размером 10, используя ключ mod 10:

5 mod 10 = 5 -> ячейка 5 12 mod 10 = 2 -> ячейка 2 22 mod 10 = 2 -> ячейка 2 занята! коллизия разрешаем цепочкой: в ячейке 2 список [12, 22]

Ключи 12 и 22 дали один индекс, поэтому их хранят в одной цепочке. При поиске 22 вычисляем индекс 2 и просматриваем короткий список.

Коэффициент заполнения

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

Где применяют хеш-таблицы

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

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

Кратко о главном

• Хеш-таблица хранит пары «ключ — значение» и быстро ищет по ключу.
• Хеш-функция превращает ключ в индекс ячейки массива.
• Коллизия — это совпадение индексов у разных ключей.
• Коллизии разрешают методом цепочек или открытой адресацией.
• В среднем операции выполняются за постоянное время.