6.5 KiB
Хеш-коллизии
Как упоминалось в предыдущем разделе, в обычных условиях входное пространство хеш-функции значительно больше выходного пространства, поэтому хеш-коллизии теоретически неизбежны. Например, если входное пространство состоит из всех целых чисел, а выходное пространство соответствует размеру массива, то обязательно несколько целых чисел будут отображаться в один и тот же индекс корзины.
Хеш-коллизии могут привести к ошибкам в результатах запросов, серьезно влияя на работоспособность хеш-таблицы. Чтобы решить эту проблему, при возникновении хеш-коллизий выполняется увеличение емкости хеш-таблицы до тех пор, пока коллизии не исчезнут. Этот метод понятен и прост в реализации, но крайне неэффективен, поскольку увеличение емкости хеш-таблицы требует значительных затрат на перенос данных и вычисление хеш-значений. Для повышения эффективности можно использовать следующие стратегии:
- Улучшение структуры данных хеш-таблицы, чтобы она могла нормально функционировать при возникновении хеш-коллизий.
- Выполнение увеличения емкости только при необходимости, т. е. когда хеш-коллизии становятся достаточно серьезными.
Основные методы улучшения структуры хеш-таблицы включают цепную адресацию и открытую адресацию.
Цепная адресация
В исходной хеш-таблице каждая корзина может хранить только одну пару ключ--значение. Цепная адресация преобразует отдельный элемент в связный список, где пары ключ--значение выступают в качестве узлов списка, и все пары ключ--значение, вызвавшие коллизии, хранятся в одном и том же списке. На рис. 6.5 представлен пример хеш-таблицы с цепной адресацией.
Методы работы с хеш-таблицей, реализованной на основе цепной адресации, изменяются следующим образом.
- Поиск элемента: вводится ключ, с помощью хеш-функции определяется индекс корзины, после чего осуществляется доступ к головному узлу списка. Затем выполняется обход списка и сравнение ключей для поиска целевой пары ключ--значение.
- Добавление элемента: сначала с помощью хеш-функции осуществляется доступ к головному узлу списка, затем узел (пара ключ--значение) добавляется в список.
- Удаление элемента: на основе результата хеш-функции осуществляется доступ к головному узлу списка, затем выполняется обход списка для поиска целевого узла и его удаления.
Цепная адресация имеет следующие ограничения.
- Увеличение занимаемого пространства: связный список содержит указатели на узлы, что требует больше памяти по сравнению с массивом.
- Снижение эффективности поиска: поскольку необходимо линейно обходить список для поиска соответствующего элемента.
[file]{hash_map_chaining}-[class]{hash_map_chaining}-[func]{}