hello-algo/ru/docs/chapter_hashing/hash_map.md

Хеш-таблицы

Хеш-таблица реализует эффективный поиск элементов через установление соответствия между ключом 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.

index = hash(key) % capacity

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

Предположим, что длина массива capacity = 100, хеш-алгоритм hash(key) = key. Тогда хеш-функция будет иметь вид key % 100. На рисунке ниже показан принцип работы хеш-функции на примере ключа «номер» и значения «имя» для студента.

В коде ниже реализуется простая хеш-таблица. Здесь key и value заключены в класс Pair для представления пары ключ--значение.

[file]{array_hash_map}-[class]{array_hash_map}-[func]{}

Хеш-коллизии и расширение

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

Для хеш-функции в примере выше, если последние две цифры ключа совпадают, результат хеш-функции также совпадает. Например, при запросе студентов с номерами 12836 и 20336 мы получим:

12836 % 100 = 36
20336 % 100 = 36

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

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

Как показано на рисунке ниже, до увеличения емкости пары ключ--значение (136, A) и (236, D) попадали в одну корзину, а после увеличения емкости коллизия исчезла.

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

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