# Хеш-таблицы
Хеш-таблица реализует эффективный поиск элементов через установление соответствия между ключом `key` и значением `value`. Более конкретно, передав ключ в хеш-таблицу, можно получить соответствующее значение за время $O(1)$.
Пусть имеется $n$ студентов, у каждого из которых есть имя и номер. Если нужно реализовать функцию «ввести номер студента и получить соответствующее имя», то можно использовать хеш-таблицу, как показано на рисунке ниже.
Помимо хеш-таблиц, функцией поиска также обладают массивы и связные списки. Сравнение их эффективности приведено в таблице ниже.
- **Добавление элемента**: достаточно добавить элемент в конец массива (списка) за время $O(1)$.
- **Поиск элемента**: так как массив (список) не упорядочен, необходимо просмотреть все элементы за время $O(n)$.
- **Удаление элемента**: сначала нужно найти элемент, а затем удалить его из массива (списка), понадобится время $O(n)$.
Таблица Сравнение эффективности поиска элементов
| | Массив | Связный список | Хеш-таблица |
| --------------------- | -------- | -------------- | ----------- |
| Поиск элемента | $O(n)$ | $O(n)$ | $O(1)$ |
| Добавление элемента | $O(1)$ | $O(1)$ | $O(1)$ |
| Удаление элемента | $O(n)$ | $O(n)$ | $O(1)$ |
Мы видим, **что в хеш-таблице операции добавления, удаления и поиска имеют временную сложность $O(1)$**, что очень эффективно.
## Основные операции с хеш-таблицами
К основным операциям с хеш-таблицами относятся: инициализация, поиск, добавление и удаление пар ключ--значение. Ниже приведен пример кода.
=== "Python"
```python title="hash_map.py"
# Инициализация хеш-таблицы
hmap: dict = {}
# Операция добавления
# Добавление пары ключ-значение (key, value) в хеш-таблицу
hmap[12836] = "Иван"
hmap[15937] = "Петр"
hmap[16750] = "Владимир"
hmap[13276] = "Максим"
hmap[10583] = "Андрей"
# Операция поиска
# Ввод ключа key в хеш-таблицу для получения значения value
name: str = hmap[15937]
# Операция удаления
# Удаление пары ключ-значение (key, value) из хеш-таблицы
hmap.pop(10583)
```
??? pythontutor "可视化运行"
https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%9F%A5%E8%AF%A2%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%90%91%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E8%BE%93%E5%85%A5%E9%94%AE%20key%20%EF%BC%8C%E5%BE%97%E5%88%B0%E5%80%BC%20value%0A%20%20%20%20name%20%3D%20hmap%5B15937%5D%0A%20%20%20%20%0A%20%20%20%20%23%20%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E5%88%A0%E9%99%A4%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap.pop%2810583%29&cumulative=false&curInstr=2&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
Существует три распространенных способа обхода хеш-таблицы: обход пар ключ--значение, обход ключей и обход значений. Ниже приведен пример кода.
=== "Python"
```python title="hash_map.py"
# Обход хеш-таблицы
# Обход пар ключ-значение key->value
for key, value in hmap.items():
print(key, "->", value)
# Обход только ключей key
for key in hmap.keys():
print(key)
# Обход только значений value
for value in hmap.values():
print(value)
```
??? pythontutor "可视化运行"
https://pythontutor.com/render.html#code=%22%22%22Driver%20Code%22%22%22%0Aif%20__name__%20%3D%3D%20%22__main__%22%3A%0A%20%20%20%20%23%20%E5%88%9D%E5%A7%8B%E5%8C%96%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20hmap%20%3D%20%7B%7D%0A%20%20%20%20%0A%20%20%20%20%23%20%E6%B7%BB%E5%8A%A0%E6%93%8D%E4%BD%9C%0A%20%20%20%20%23%20%E5%9C%A8%E5%93%88%E5%B8%8C%E8%A1%A8%E4%B8%AD%E6%B7%BB%E5%8A%A0%E9%94%AE%E5%80%BC%E5%AF%B9%20%28key,%20value%29%0A%20%20%20%20hmap%5B12836%5D%20%3D%20%22%E5%B0%8F%E5%93%88%22%0A%20%20%20%20hmap%5B15937%5D%20%3D%20%22%E5%B0%8F%E5%95%B0%22%0A%20%20%20%20hmap%5B16750%5D%20%3D%20%22%E5%B0%8F%E7%AE%97%22%0A%20%20%20%20hmap%5B13276%5D%20%3D%20%22%E5%B0%8F%E6%B3%95%22%0A%20%20%20%20hmap%5B10583%5D%20%3D%20%22%E5%B0%8F%E9%B8%AD%22%0A%20%20%20%20%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E5%93%88%E5%B8%8C%E8%A1%A8%0A%20%20%20%20%23%20%E9%81%8D%E5%8E%86%E9%94%AE%E5%80%BC%E5%AF%B9%20key-%3Evalue%0A%20%20%20%20for%20key,%20value%20in%20hmap.items%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key,%20%22-%3E%22,%20value%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E9%94%AE%20key%0A%20%20%20%20for%20key%20in%20hmap.keys%28%29%3A%0A%20%20%20%20%20%20%20%20print%28key%29%0A%20%20%20%20%23%20%E5%8D%95%E7%8B%AC%E9%81%8D%E5%8E%86%E5%80%BC%20value%0A%20%20%20%20for%20value%20in%20hmap.values%28%29%3A%0A%20%20%20%20%20%20%20%20print%28value%29&cumulative=false&curInstr=8&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=311&rawInputLstJSON=%5B%5D&textReferences=false
## Простая реализация хеш-таблицы
Рассмотрим самый простой случай, **когда хеш-таблица реализуется с помощью одного массива**. В хеш-таблице каждый пустой слот массива называется корзиной, и каждая корзина может хранить одну пару ключ--значение. Таким образом, операция поиска заключается в нахождении корзины, соответствующей ключу `key`, и получении значения `value` из нее.
Как определить корзину, соответствующую ключу? Это осуществляется с помощью хеш-функции. Хеш-функция предназначена для отображения большого входного пространства в меньшее выходное пространство. В хеш-таблице входное пространство -- это все ключи, а выходное пространство -- это все корзины (индексы массива). Другими словами, **передав ключ в хеш-функцию, можно определить место хранения пары ключ--значение в массиве**.
Процесс вычисления хеш-функции для ключа включает следующие этапы:
1. вычисление хеш-значения с помощью некоторого хеш-алгоритма `hash()`;
2. взятие остатка от деления хеш-значения на количество корзин `capacity` (длину массива) для получения индекса массива `index`, соответствующего ключу `key`.
```shell
index = hash(key) % capacity
```
После этого можно использовать значение `index` для доступа к соответствующей корзине в хеш-таблице и получения значения `value`.
Предположим, что длина массива `capacity = 100`, хеш-алгоритм `hash(key) = key`. Тогда хеш-функция будет иметь вид `key % 100`. На рисунке ниже показан принцип работы хеш-функции на примере ключа «номер» и значения «имя» для студента.
В коде ниже реализуется простая хеш-таблица. Здесь `key` и `value` заключены в класс `Pair` для представления пары ключ--значение.
```src
[file]{array_hash_map}-[class]{array_hash_map}-[func]{}
```
## Хеш-коллизии и расширение
По своей сути хеш-функция выполняет отображение входного пространства, состоящего из всех ключей, в выходное пространство, состоящее из всех индексов массива. Причем входное пространство зачастую значительно больше выходного. Следовательно, **теоретически неизбежна ситуация, когда несколько входов соответствуют одному выходу**.
Для хеш-функции в примере выше, если последние две цифры ключа совпадают, результат хеш-функции также совпадает. Например, при запросе студентов с номерами 12836 и 20336 мы получим:
```shell
12836 % 100 = 36
20336 % 100 = 36
```
Оба номера указывают на одно и то же имя, что очевидно неверно. Такую ситуацию, когда несколько входов соответствуют одному выходу, называют хеш-коллизией.
Логично предположить, что чем больше емкость хеш-таблицы $n$, тем ниже вероятность распределения нескольких ключей в одну корзину и тем меньше коллизий. Поэтому **можно уменьшить количество хеш-коллизий, увеличивая емкость хеш-таблицы**.
Как показано на рисунке ниже, до увеличения емкости пары ключ--значение `(136, A)` и `(236, D)` попадали в одну корзину, а после увеличения емкости коллизия исчезла.
Подобно увеличению емкости массива, увеличение емкости хеш-таблицы требует переноса всех пар ключ--значение из старой хеш-таблицы в новую, что является очень затратной по времени операцией. Кроме того, поскольку емкость хеш-таблицы изменяется, необходимо заново вычислять местоположение хранения всех пар ключ--значение с помощью хеш-функции, что еще больше увеличивает вычислительные затраты процесса расширения. Поэтому в языках программирования обычно резервируется достаточно большая емкость хеш-таблицы, чтобы избежать частого увеличения.
Коэффициент заполнения является важным понятием для хеш-таблицы. Он определяется как количество элементов в хеш-таблице, деленное на количество корзин, и используется для оценки степени серьезности хеш-коллизий, **а также часто служит условием для увеличения емкости хеш-таблицы**. Например, в Java, когда коэффициент заполнения превышает $0.75$, система увеличивает емкость хеш-таблицы в $2$ раза.