# Хеш-коллизии

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

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

1. Улучшение структуры данных хеш-таблицы, **чтобы она могла нормально функционировать при возникновении хеш-коллизий**.
2. Выполнение увеличения емкости только при необходимости, т. е. когда хеш-коллизии становятся достаточно серьезными.

Основные методы улучшения структуры хеш-таблицы включают цепную адресацию и открытую адресацию.

## Цепная адресация

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

![Хеш-таблица с цепной адресацией](../assets/media/image203.jpeg)

Методы работы с хеш-таблицей, реализованной на основе цепной адресации, изменяются следующим образом.

- **Поиск элемента**: вводится ключ, с помощью хеш-функции определяется индекс корзины, после чего осуществляется доступ к головному узлу списка. Затем выполняется обход списка и сравнение ключей для поиска целевой пары ключ--значение.
- **Добавление элемента**: сначала с помощью хеш-функции осуществляется доступ к головному узлу списка, затем узел (пара ключ--значение) добавляется в список.
- **Удаление элемента**: на основе результата хеш-функции осуществляется доступ к головному узлу списка, затем выполняется обход списка для поиска целевого узла и его удаления.

Цепная адресация имеет следующие ограничения.

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

<!-- 🔴 俄文版缺失此段落 -->
<!-- 中文原文：以下代码给出了链式地址哈希表的简单实现，需要注意两点。使用列表（动态数组）代替链表，从而简化代码。在这种设定下，哈希表（数组）包含多个桶，每个桶都是一个列表。以下实现包含哈希表扩容方法。当负载因子超过 2/3 时，我们将哈希表扩容至原先的 2 倍... -->

```src
[file]{hash_map_chaining}-[class]{hash_map_chaining}-[func]{}
```

<!-- 🔴 俄文版缺失此段落 -->
<!-- 中文原文：值得注意的是，当链表很长时，查询效率 O(n) 很差。此时可以将链表转换为"AVL 树"或"红黑树"，从而将查询操作的时间复杂度优化至 O(log n)... -->

## Открытая адресация

<!-- 🔴 俄文版缺失此段落 -->
<!-- 中文原文：开放寻址（open addressing）不引入额外的数据结构，而是通过"多次探测"来处理哈希冲突，探测方式主要包括线性探测、平方探测和多次哈希等... -->

<!-- 🔴 俄文版缺失此段落 -->
<!-- 中文原文：下面以线性探测为例，介绍开放寻址哈希表的工作机制... -->

### Линейная проба

<!-- 🔴 俄文版缺失完整的线性探测部分内容 -->

### Квадратичная проба

<!-- 🔴 俄文版缺失完整的平方探测部分内容 -->

### Множественное хеширование

<!-- 🔴 俄文版缺失完整的多次哈希部分内容 -->

## Выбор языка программирования

<!-- 🔴 俄文版缺失此段落 -->
<!-- 中文原文：各种编程语言采取了不同的哈希表实现策略，下面举几个例子。Python 采用开放寻址。字典 dict 使用伪随机数进行探测。Java 采用链式地址... -->