# Хеш-таблицы

![](ru/docs/assets/media/image193.jpeg){width="3.8073009623797027in" height="4.927083333333333in"}

#### хеш-таблицы

> *Хеш-таблица* реализует эффективный поиск элементов через установле- ние соответствия между ключом key и значением value. Более конкретно, передав ключ в хеш-таблицу, можно получить соответствующее значение за время *O*(1).
>
> Пусть имеется *n* студентов, у каждого из которых есть имя и номер. Если нужно реализовать функцию «ввести номер студента и получить соответству- ющее имя», то можно использовать хеш-таблицу, как показано на рис. 6.1.

![](ru/docs/assets/media/image195.jpeg)

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

- **Добавление элемента**: достаточно добавить элемент в конец массива (списка) за время *O*(1).

- **Поиск элемента**: так как массив (список) не упорядочен, необходимо просмотреть все элементы за время *O*(*n*).

- **Удаление элемента**: сначала нужно найти элемент, а затем удалить его из массива (списка), понадобится время *O*(*n*).

> **Таблица 6.1.** Сравнение эффективности поиска элементов

+-----------------------+--------------+----------------------+-------------------+
|                       | > **Массив** | > **Связный список** | > **Хеш-таблица** |
+=======================+:============:+:====================:+:=================:+
| > Поиск элемента      | > *O*(*n*)   | > *O*(*n*)           | > *O*(1)          |
+-----------------------+--------------+----------------------+-------------------+
| > Добавление элемента | > *O*(1)     | > *O*(1)             | > *O*(1)          |
+-----------------------+--------------+----------------------+-------------------+
| > Удаление элемента   | > *O*(*n*)   | > *O*(*n*)           | > *O*(1)          |
+-----------------------+--------------+----------------------+-------------------+

> Мы видим, **что в хеш-таблице операции добавления**, **удаления и поис- ка имеют временную сложность** *O*(1), что очень эффективно.

1.  **Основные операции с хеш-таблицами**

> К основным операциям с хеш-таблицами относятся: инициализация, поиск, добавление и удаление пар ключ--значение. Ниже приведен пример кода.
>
> \# === File: 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)
>
> Существует три распространенных способа обхода хеш-таблицы: обход пар ключ--значение, обход ключей и обход значений. Ниже приведен пример кода.
>
> \# === File: 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)

### Простая реализация хеш-таблицы

> Рассмотрим самый простой случай, **когда хеш-таблица реализуется с помо- щью одного массива**. В хеш-таблице каждый пустой слот массива называется корзиной, и каждая корзина может хранить одну пару ключ--значение. Таким образом, операция поиска заключается в нахождении корзины, соответствую- щей ключу key, и получении значения value из нее.
>
> Как определить корзину, соответствующий ключу? Это осуществляется с по- мощью хеш-функции. Хеш-функция предназначена для отображения большо- го входного пространства в меньшее выходное пространство. В хеш-таблице входное пространство -- это все ключи, а выходное пространство -- это все кор- зины (индексы массива). Другими словами, **передав ключ в хеш-функцию, можно определить место хранения пары ключ--значение в массиве**.
>
> Процесс вычисления хеш-функции для ключа включает следующие этапы:

1)  вычисление хеш-значения с помощью некоторого хеш-алгоритма hash();

2)  взятие остатка от деления хеш-значения на количество корзин capacity (длину массива) для получения индекса массива index, соответствующе- го ключу key.

> index = hash(key) % capacity
>
> После этого можно использовать значение index для доступа к соответству- ющей корзине в хеш-таблице и получения значения value.
>
> Предположим, что длина массива capacity = 100, хеш-алгоритм hash(key) = key. Тогда хеш-функция будет иметь вид key % 100. На рис. 6.2 показан принцип ра- боты хеш-функции на примере ключа «номер» и значения «имя» для студента.
>
> ![](ru/docs/assets/media/image197.jpeg) **Ввод key**
>
> **Индекс Массив**
>
> **Вывод value**
>
> \"Иван\" \"Иван\"
>
> \"Петр\"

Хеш-функция

> \"Яков\" \"Яков\"
>
> \"Ира\" \"Ира\"
>
> \"Аня\"
>
> (Каждая ячейка хранит одну пару ключ--значение)
>
> **Рис. 6.2.** Принцип работы хеш-функции
>
> В коде ниже реализуется простая хеш-таблица. Здесь key и value заключены в класс Pair для представления пары ключ--значение.
>
> \# === File: array_hash_map.py === class Pair:
>
> \"\"\" Пара ключ-значение.\"\"\"
>
> def init (self, key: int, val: str): self.key = key
>
> self.val = val
>
> class ArrayHashMap:
>
> \"\"\" Хеш-таблица на основе массива.\"\"\"
>
> def init (self):
>
> \"\"\" Конструктор.\"\"\"
>
> \# Инициализация массива, содержащего 100 корзин. self.buckets: list\[Pair \| None\] = \[None\] \* 100
>
> def hash_func(self, key: int) -\> int: \"\"\" Хеш-функция.\"\"\"
>
> index = key % 100 return index
>
> def get(self, key: int) -\> str: \"\"\" Операция поиска.\"\"\"
>
> index: int = self.hash_func(key) pair: Pair = self.buckets\[index\] if pair is None:
>
> return None return pair.val
>
> def put(self, key: int, val: str): \"\"\" Операция добавления.\"\"\" pair = Pair(key, val)
>
> index: int = self.hash_func(key) self.buckets\[index\] = pair
>
> def remove(self, key: int): \"\"\" Операция удаления.\"\"\"
>
> index: int = self.hash_func(key)
>
> \# Установка в None означает удаление. self.buckets\[index\] = None
>
> def entry_set(self) -\> list\[Pair\]:
>
> \"\"\" Получение всех пар ключ-значение.\"\"\" result: list\[Pair\] = \[\]
>
> for pair in self.buckets: if pair is not None:
>
> result.append(pair) return result
>
> def key_set(self) -\> list\[int\]: \"\"\" Получение всех ключей.\"\"\" result = \[\]
>
> for pair in self.buckets: if pair is not None:
>
> result.append(pair.key) return result
>
> def value_set(self) -\> list\[str\]: \"\"\" Получение всех значений.\"\"\" result = \[\]
>
> for pair in self.buckets: if pair is not None:
>
> result.append(pair.val) return result
>
> def print(self):
>
> \"\"\" Печать хеш-таблицы.\"\"\" for pair in self.buckets:
>
> if pair is not None: print(pair.key, \"-\>\", pair.val)

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

> По своей сути хеш-функция выполняет отображение входного пространства, состоящего из всех ключей, в выходное пространство, состоящее из всех ин- дексов массива. Причем входное пространство зачастую значительно больше выходного. Следовательно, **теоретически неизбежна ситуация**, **когда не- сколько входов соответствуют одному выходу**.
>
> Для хеш-функции в примере выше, если последние две цифры ключа совпа- дают, результат хеш-функции также совпадает. Например, при запросе студен- тов с номерами 12836 и 20336 мы получим:
>
> 12836 % 100 = 36
>
> 20336 % 100 = 36.
>
> Оба номера указывают на одно и то же имя, что очевидно неверно, см. рис. 6.3. Такую ситуацию, когда несколько входов соответствуют одному вы- ходу, называют хеш-коллизией.
>
> ![](ru/docs/assets/media/image199.jpeg) **Ввод key**
>
> **Индекс Массив Хеш-коллизия**
>
> **Вывод value**
>
> \"Иван\"

Хеш-функция

\"Петр\"

\"Яков\"

> \"Иван\"
>
> \"Иван\"
>
> \"Ира\"
>
> \"Аня\"
>
> (Каждая ячейка хранит одну пару ключ--значение)
>
> **Рис. 6.3.** Пример хеш-коллизии
>
> Логично предположить, что чем больше емкость хеш-таблицы *n*, тем ниже вероятность распределения нескольких ключей в одну корзину и тем меньше коллизий. Поэтому **можно уменьшить количество хеш-коллизий**, **увели- чивая емкость хеш-таблицы**.
>
> Как показано на рис. 6.4, до увеличения емкости пары ключ--значение (136, A)

и (236, D) попадали в одну корзину, а после увеличения емкости коллизия исчезла.

> ![](ru/docs/assets/media/image201.jpeg)**Увеличение хеш-таблицы**
>
> **Рис. 6.4.** Увеличение емкости хеш-таблицы
>
> Подобно увеличению емкости массива, увеличение емкости хеш-таблицы требует переноса всех пар ключ--значение из старой хеш-таблицы в новую, что является очень затратной по времени операцией. Кроме того, поскольку емкость хеш-таблицы изменяется, необходимо заново вычислять местополо- жение хранения всех пар ключ--значение с помощью хеш-функции, что еще больше увеличивает вычислительные затраты процесса расширения. Поэтому в языках программирования обычно резервируется достаточно большая ем- кость хеш-таблицы, чтобы избежать частого увеличения.
>
> Коэффициент заполнения является важным понятием для хеш-таблицы. Он определяется как количество элементов в хеш-таблице, деленное на коли- чество корзин, и используется для оценки степени серьезности хеш-коллизий, **а также часто служит условием для увеличения емкости хеш-таблицы**. Например, в Java, когда коэффициент заполнения превышает 0.75, система увеличивает емкость хеш-таблицы в 2 раза.

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

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

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

2)  выполнение увеличения емкости только при необходимости, т. е. когда хеш-коллизии становятся достаточно серьезными.

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

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

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

![](ru/docs/assets/media/image203.jpeg)

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

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

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

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

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

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

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

> Ниже приведен простой пример реализации хеш-таблицы с цепной адреса- цией. Следует обратить внимание на следующие моменты.

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

- В данной реализации предусмотрен метод расширения хеш-таблицы. Когда коэффициент заполнения превышает 2/3, хеш-таблица расширя- ется в 2 раза.

> \# === File: hash_map_chaining.py === class HashMapChaining:
>
> \"\"\" Хеш-таблица с цепной адресацией.\"\"\"
>
> def init (self):
>
> \"\"\" Конструктор.\"\"\"
>
> self.size = 0 \# Количество пар ключ-значение. self.capacity = 4 \# Вместимость хеш-таблицы.
>
> self.load_thres = 2.0 / 3.0 \# Порог коэффициента заполнения для расши-
>
> рения.
>
> self.extend_ratio = 2 \# Коэффициент расширения.
>
> self.buckets = \[\[\] for \_ in range(self.capacity)\] \# Массив корзин.
>
> def hash_func(self, key: int) -\> int: \"\"\" Хеш-функция.\"\"\"
>
> return key % self.capacity
>
> def load_factor(self) -\> float:
>
> \"\"\" Коэффициент заполнения.\"\"\" return self.size / self.capacity
>
> def get(self, key: int) -\> str \| None: \"\"\" Операция поиска.\"\"\"
>
> index = self.hash_func(key) bucket = self.buckets\[index\]
>
> \# Обход корзины, если ключ найден, возвращается соответствующее значение. for pair in bucket:
>
> if pair.key == key: return pair.val
>
> \# Если ключ не найден, возвращается None. return None
>
> def put(self, key: int, val: str): \"\"\" Операция добавления.\"\"\"
>
> \# При превышении коэффициента заполнения выполняется расширение. if self.load_factor() \> self.load_thres:
>
> self.extend()
>
> index = self.hash_func(key) bucket = self.buckets\[index\]
>
> \# Обход корзины; если ключ найден, значение обновляется \# и выполняется выход из функции.
>
> for pair in bucket:
>
> if pair.key == key: pair.val = val return
>
> \# Если ключ отсутствует, пара ключ-значение добавляется в конец. pair = Pair(key, val)
>
> bucket.append(pair) self.size += 1
>
> def remove(self, key: int): \"\"\" Операция удаления.\"\"\"
>
> index = self.hash_func(key) bucket = self.buckets\[index\]
>
> \# Обход корзины, удаление пары ключ-значение. for pair in bucket:
>
> if pair.key == key: bucket.remove(pair) self.size -= 1 break
>
> def extend(self):
>
> \"\"\" Расширение хеш-таблицы.\"\"\"
>
> \# Сохранение исходной хеш-таблицы. buckets = self.buckets
>
> \# Инициализация новой расширенной хеш-таблицы. self.capacity \*= self.extend_ratio
>
> self.buckets = \[\[\] for \_ in range(self.capacity)\] self.size = 0
>
> \# Перенос пар ключ-значение из исходной хеш-таблицы в новую. for bucket in buckets:
>
> for pair in bucket: self.put(pair.key, pair.val)
>
> def print(self):
>
> \"\"\" Печать хеш-таблицы.\"\"\" for bucket in self.buckets:
>
> res = \[\]
>
> for pair in bucket:
>
> res.append(str(pair.key) + \" -\> \" + pair.val) print(res)
>
> Стоит отметить, что в длинных списках эффективность поиска *O*(*n*) весьма низка. В этом случае **можно преобразовать список в АВЛ-дерево или крас- но-черное дерево**, чтобы оптимизировать временную сложность операции поиска до *O*(log *n*).

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

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

##### Линейное зондирование

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

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

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

> На рис. 6.6 демонстрируется распределение пар ключ--значение в хеш- таблице с открытой адресацией (линейное зондирование). Согласно этой хеш- функции ключи с одинаковыми последними двумя цифрами отображаются в одну корзину. Однако благодаря линейному зондированию они последова- тельно размещаются в этой и следующих корзинах.
>
> Однако линейное зондирование **подвержено так называемой класте- ризации**. Чем длиннее последовательность занятых позиций в массиве, тем выше вероятность хеш-конфликта в этих позициях. Это способствует дальней- шему росту кластера, создавая порочный круг и в конечном итоге снижая эф- фективность операций добавления, удаления и поиска.
>
> Стоит отметить, что **в хеш-таблице с открытой адресацией нельзя на- прямую удалять элементы**. Это связано с тем, что удаление элемента соз- дает в массиве пустую корзину None. И затем при поиске элемента линейное зондирование, достигнув этой пустой корзины, закончит поиск, что приведет к невозможности доступа к элементам ниже этой корзины. Программа может ошибочно посчитать, что эти элементы отсутствуют, как показано на рис. 6.7.
>
> ![](ru/docs/assets/media/image205.jpeg)
>
> **Рис. 6.6.** Распределение пар ключ--значение в хеш-таблице с открытой адресацией (линейное зондирование)

![](ru/docs/assets/media/image207.jpeg)

> **Рис. 6.7.** Проблемы поиска, вызванные удалением элементов при открытой адресации
>
> Для решения этой проблемы можно использовать механизм ленивого удаления: элементы не удаляются из хеш-таблицы напрямую, **вместо это- го для пометки этой корзины используется константа** TOMBSTONE. При та- ком подходе None и TOMBSTONE обозначают пустую корзину, в которую можно поместить пару ключ--значение. Однако при линейном зондировании зна- чение TOMBSTONE не завершает обход, так как ниже все еще могут находиться пары ключ--значение.
>
> Однако **ленивое удаление может ускорить падение производительно- сти хеш-таблицы**. Это происходит потому, что каждая операция удаления оставляет метку удаления, и с увеличением количества значений TOMBSTONE время поиска также увеличивается, поскольку при линейном зондировании может потребоваться пропуск нескольких TOMBSTONE.
>
> В качестве решения предлагается при линейном зондировании фиксиро- вать индекс первого встретившегося TOMBSTONE и менять местами найденный целевой элемент с этим TOMBSTONE. Преимущество такого подхода заключает- ся в том, что при каждом запросе или добавлении элемента он перемещается в корзину, находящуюся ближе к идеальному положению (начальной точке по- иска), что оптимизирует эффективность запросов.
>
> В следующем коде реализована хеш-таблица с открытой адресацией (ли- нейным зондированием), включающей ленивое удаление. Для более полного использования пространства хеш-таблицы она рассматривается как кольце- вой массив, и при переходе за конец массива происходит возврат к началу.
>
> \# === File: hash_map_open_addressing.py === class HashMapOpenAddressing:
>
> \"\"\" Открытая адресация хеш-таблицы.\"\"\"
>
> def init (self):
>
> \"\"\" Конструктор.\"\"\"
>
> self.size = 0 \# Количество пар ключ-значение. self.capacity = 4 \# Вместимость хеш-таблицы.
>
> self.load_thres = 2.0 / 3.0 \# Порог коэффициента заполнения для расширения. self.extend_ratio = 2 \# Коэффициент расширения.
>
> self.buckets: list\[Pair \| None\] = \[None\] \* self.capacity \# Массив корзин. self.TOMBSTONE = Pair(-1, \"-1\") \# Метка удаления.
>
> def hash_func(self, key: int) -\> int: \"\"\" Хеш-функция.\"\"\"
>
> return key % self.capacity
>
> def load_factor(self) -\> float:
>
> \"\"\" Коэффициент заполнения.\"\"\" return self.size / self.capacity
>
> def find_bucket(self, key: int) -\> int:
>
> \"\"\" Поиск индекса корзины по ключу.\"\"\" index = self.hash_func(key) first_tombstone = -1
>
> \# Линейное зондирование, выход при встрече пустой корзины. while self.buckets\[index\] is not None:
>
> \# Если найден ключ, возвращается соответствующий индекс корзины. if self.buckets\[index\].key == key:
>
> \# Если ранее была метка удаления, перемещение пары
>
> \# ключ-значение в этот индекс. if first_tombstone != -1:
>
> self.buckets\[first_tombstone\] = self.buckets\[index\] self.buckets\[index\] = self.TOMBSTONE
>
> return first_tombstone \# Возврат индекса перемещенной корзины. return index \# Возврат индекса корзины.
>
> \# Фиксация первого встретившегося удаления.
>
> if first_tombstone == -1 and self.buckets\[index\] is self.TOMBSTONE: first_tombstone = index
>
> \# Вычисление индекса корзины, при переходе за конец
>
> \# возвращение к началу.
>
> index = (index + 1) % self.capacity
>
> \# Если ключ не существует, возвращается индекс для добавления. return index if first_tombstone == -1 else first_tombstone
>
> def get(self, key: int) -\> str: \"\"\" Операция запроса.\"\"\"
>
> \# Поиск индекса корзины по ключу. index = self.find_bucket(key)
>
> \# Если найдена пара ключ-значение, возвращается соответствующее значение. if self.buckets\[index\] not in \[None, self.TOMBSTONE\]:
>
> return self.buckets\[index\].val
>
> \# Если пара ключ-значение не существует, возвращается None. return None
>
> def put(self, key: int, val: str): \"\"\" Операция добавления.\"\"\"
>
> \# При превышении порога коэффициента заполнения выполняется расширение. if self.load_factor() \> self.load_thres:
>
> self.extend()
>
> \# Поиск индекса корзины по ключу. index = self.find_bucket(key)
>
> \# Если найдена пара ключ-значение, значение перезаписывается и возвращается. if self.buckets\[index\] not in \[None, self.TOMBSTONE\]:
>
> self.buckets\[index\].val = val return
>
> \# Если пара ключ-значение не существует, добавляется новая пара. self.buckets\[index\] = Pair(key, val)
>
> self.size += 1
>
> def remove(self, key: int): \"\"\" Операция удаления.\"\"\"
>
> \# Поиск индекса корзины по ключу. index = self.find_bucket(key)
>
> \# Если найдена пара ключ-значение, она заменяется меткой удаления. if self.buckets\[index\] not in \[None, self.TOMBSTONE\]:
>
> self.buckets\[index\] = self.TOMBSTONE self.size -= 1
>
> def extend(self):
>
> \"\"\" Расширение хеш-таблицы.\"\"\"
>
> \# Временное сохранение оригинальной хеш-таблицы. buckets_tmp = self.buckets
>
> \# Инициализация новой хеш-таблицы после расширения. self.capacity \*= self.extend_ratio
>
> self.buckets = \[None\] \* self.capacity self.size = 0
>
> \# Перенос пар ключ-значение из оригинальной хеш-таблицы в новую. for pair in buckets_tmp:
>
> if pair not in \[None, self.TOMBSTONE\]: self.put(pair.key, pair.val)
>
> def print(self):
>
> \"\"\" Печать хеш-таблицы.\"\"\" for pair in self.buckets:
>
> if pair is None: print(\"None\")
>
> elif pair is self.TOMBSTONE: print(\"TOMBSTONE\")
>
> else:
>
> print(pair.key, \"-\>\", pair.val)

##### Квадратичное зондирование

> Квадратичное зондирование, как и линейное, является одной из распростра- ненных стратегий открытой адресации. При возникновении конфликта ква- дратичное зондирование пропускает не просто фиксированное количество шагов, а количество шагов, равное квадрату числа попыток, т. е. 1, 4, 9, \...
>
> Квадратичное зондирование обладает следующими преимуществами:

- квадратичное зондирование, пропуская расстояние, равное квадрату числа попыток, стремится сгладить эффект кластеризации линейного зондирования;

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

> Тем не менее квадратичный поиск не является идеальным и обладает сле- дующими недостатками:

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

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

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

> Как следует из названия, метод множественного хеширования использует для поиска несколько хеш-функций *f*1(*x*), *f*2(*x*), *f*3(*x*), \...

- **Вставка элемента**: если хеш-функция *f*1(*x*) вызывает конфликт, вычис- ляется *f*2(*x*) и т. д., пока не будет найдено пустое место для вставки эле- мента.

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

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

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

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

- В Python используется метод открытой адресации. В словарях dict для поиска применяется псевдослучайное число.

- В Java используется цепная адресация. Начиная с JDK 1.8, когда длина мас- сива в HashMap достигает 64, а длина цепочки достигает 8, цепочка преоб- разуется в красно-черное дерево для повышения эффективности поиска.

- В Go используется цепная адресация. Здесь предусмотрено, что в каждой корзине может храниться не более 8 пар ключ--значение. При превыше- нии емкости подключается дополнительная корзина. При избыточном количестве дополнительных корзин выполняется специальная опера- ция расширения для поддержания производительности.

#### Алгоритмы хеширования

> В предыдущих разделах были рассмотрены принципы работы хеш-таблиц и методы обработки хеш-конфликтов. Однако ни открытая, ни цепная адре- сация не могут уменьшить вероятность возникновения хеш-конфликтов, **они лишь обеспечивают корректную работу хеш-таблицы при их воз- никновении**.
>
> Если хеш-конфликты происходят слишком часто, производительность хеш- таблицы резко снижается. Как показано на рис. 6.8, для хеш-таблицы с цепной адресацией в идеальном случае пары ключ--значение равномерно распреде- лены по всем корзинам, что обеспечивает наилучшую эффективность поиска. В худшем случае все пары ключ--значение хранятся в одной корзине, и вре- менная сложность повышается до *O*(*n*).
>
> ![](ru/docs/assets/media/image209.jpeg)
>
> **Рис. 6.8.** Лучший и худший случаи хеш-конфликтов
>
> **Распределение пар ключ--значение определяется хеш-функцией**. Вспомним этапы вычисления хеш-функции: сначала вычисляется хеш- значение, затем берется остаток от деления на длину массива.
>
> index = hash(key) % capacity
>
> Из этого выражения видно, что при фиксированной емкости хеш-таблицы capacity **алгоритм хеширования** hash() **определяет выходное значение**, которое, в свою очередь, определяет распределение пар ключ--значение в хеш-таблице.
>
> Это означает, что для снижения вероятности возникновения хеш-конфликтов следует сосредоточиться на разработке алгоритма хеширования hash().

### Цели алгоритма хеширования

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

- **Детерминированность**: для одинакового ввода алгоритм хеширования должен всегда давать одинаковый вывод. Это необходимо для обеспече- ния надежности работы хеш-таблицы.

- **Высокая эффективность**: процесс вычисления хеш-значения должен быть достаточно быстрым. Чем меньше вычислительные затраты, тем выше практическая ценность хеш-таблицы.

- **Равномерное распределение**: алгоритм хеширования должен обе- спечивать равномерное распределение пар ключ--значение в хеш- таблице. Чем равномернее распределение, тем ниже вероятность хеш- конфликтов.

> На практике алгоритмы хеширования применяются не только для реализа- ции хеш-таблиц, но и в других областях.

- **Хранение паролей**: для защиты паролей пользователей система обыч- но не хранит пароли в открытом виде, а сохраняет их хеш-значения. Когда пользователь вводит пароль, система вычисляет его хеш-значение и сравнивает с сохраненным. Если они совпадают, пароль считается правильным.

- **Проверка целостности данных**: отправитель данных может вычис- лить хеш-значение данных и отправить его вместе с данными. По- лучатель может заново вычислить хеш-значение полученных данных и сравнить его с полученным. Если они совпадают, данные считаются неизмененными.

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

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

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

- **Эффект лавины**: небольшие изменения на входе должны приводить к значительным и непредсказуемым изменениям на выходе.

> Следует отметить, что **«равномерное распределение» и «устойчивость к коллизиям»** -- это два независимых понятия, и выполнение одного из них не обязательно означает выполнение другого. Например, хеш-функция key % 100 при случайном вводе значения key может давать равномерное распределение. Однако этот алгоритм хеширования слишком прост, и все ключи с одинаковыми последними двумя цифрами будут иметь одинако- вый вывод, что позволяет легко извлечь пригодные ключи из хеш-значения и взломать пароль.

### Разработка алгоритма хеширования

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

- **Аддитивный хеш**: складываются ASCII-коды каждого символа входных данных, полученная сумма используется в качестве хеш-значения.

- **Мультипликативный хеш**: используя свойство некоррелированности умножения, на каждом шаге значение хеша умножается на константу, и в результат добавляется ASCII-код очередного символа.

- **Хеш с использованием операции XOR**: каждый элемент входных дан- ных накапливается в хеш-значении с помощью операции XOR.

- **Ротационный хеш**: ASCII-коды каждого символа накапливаются в хеш- значении, при этом перед каждым накоплением выполняется операция ротации хеш-значения.

> \# === File: simple_hash.py ===
>
> def add_hash(key: str) -\> int: \"\"\" Аддитивный хеш.\"\"\" hash = 0
>
> modulus = 1000000007 for c in key:
>
> hash += ord(c) return hash % modulus
>
> def mul_hash(key: str) -\> int: \"\"\" Мультипликативный хеш.\"\"\" hash = 0
>
> modulus = 1000000007 for c in key:
>
> hash = 31 \* hash + ord(c) return hash % modulus
>
> def xor_hash(key: str) -\> int:
>
> \"\"\" Хеш с использованием операции XOR.\"\"\" hash = 0
>
> modulus = 1000000007 for c in key:
>
> hash \^= ord(c) return hash % modulus
>
> def rot_hash(key: str) -\> int: \"\"\" Ротационный хеш.\"\"\" hash = 0
>
> modulus = 1000000007 for c in key:
>
> hash = (hash \<\< 4) \^ (hash \>\> 28) \^ ord(c) return hash % modulus
>
> Можно заметить, что последним шагом в каждом из хеш-алгоритмов явля- ется взятие остатка от деления на большое простое число 1000000007, чтобы гарантировать, что хеш-значение находится в допустимом диапазоне. Инте- ресно, почему акцент делается на взятии остатка от деления именно на про- стое число, и какие недостатки могут быть при делении на составное число?
>
> Ответ: **использование большого простого числа в качестве модуля позволяет обеспечить максимально равномерное распределение хеш- значений**. Поскольку простое число не имеет общих делителей с другими числами, это позволяет уменьшить периодические закономерности, возника- ющие из-за операции взятия остатка, и избежать хеш-конфликтов.
>
> Например, если выбрать в качестве модуля составное число 9, кото- рое делится на 3, то все ключи, делящиеся на 3, будут отображаться в хеш- значения 0, 3 и 6:
>
> modulus = 9
>
> key = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \... }
>
> hash = {0, 3, 6, 0, 3, 6, 0, 3, 6, 0, 3, 6, \... }.
>
> Если входные ключи имеют такую арифметическую прогрессию, то хеш- значения будут сгруппированы, что умножит хеш-конфликты. Теперь если за- менить modulus на простое число 13, то, поскольку между ключами и модулем нет общих делителей, равномерность распределения хеш-значений значи- тельно улучшится:
>
> modulus = 13
>
> key = {0, 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, \... }
>
> hash = {0, 3, 6, 9, 12, 2, 5, 8, 11, 1, 4, 7, \... }.
>
> Следует отметить, что если ключи распределены случайно и равномерно, то выбор простого или составного числа в качестве модуля не имеет значения -- оба варианта обеспечат равномерное распределение хеш-значений. Однако при наличии периодичности в распределении ключей использование состав- ного числа в качестве модуля может привести к кластеризации.
>
> В общем случае выбирается простое число в качестве модуля, и это простое число должно быть достаточно большим, чтобы максимально устранить пери- одические закономерности и повысить устойчивость хеш-алгоритма.

### Распространенные хеш-алгоритмы

> Нетрудно заметить, что описанные выше простые хеш-алгоритмы довольно хрупкие и далеки от достижения целей создания хеш-алгоритмов. Например, сложение и операция XOR удовлетворяют коммутативному закону, поэтому соответствующие хеш-алгоритмы не различают строки с одинаковым содер- жанием, но разным порядком символов, что может усилить хеш-конфликты и вызвать некоторые проблемы с безопасностью.
>
> На практике обычно используются стандартные хеш-алгоритмы, такие как MD5, SHA-1, SHA-2 и SHA-3. Они могут отображать входные данные произ- вольной длины в хеш-значения фиксированной длины.
>
> На протяжении почти ста лет хеш-алгоритмы постоянно обновляются и оп- тимизируются. Одни исследователи стремятся повысить производительность, другие исследователи и хакеры сосредоточены на поиске проблем с безопас- ностью. В табл. 6.2 представлены распространенные хеш-алгоритмы, исполь- зуемые в реальных приложениях.

- В MD5 и SHA-1 были обнаружены многочисленные уязвимости, поэтому они не используются в сценариях, в которых требуется высокий уровень безопасности.

- SHA-256 из серии SHA-2 является одним из самых безопасных хеш- алгоритмов, до сих пор не было обнаружено ни одной уязвимости, по- этому он часто используется в различных приложениях и протоколах безопасности.

<!-- -->

- SHA-3 имеет меньшие затраты на реализацию и более высокую вычис- лительную эффективность по сравнению с SHA-2, но в настоящее время его использование не так широко распространено, как серии SHA-2.

+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+
|                          | > **MD5**                                                        | > **SHA-1**    | > **SHA-2**           | > **SHA-3**                                      |
+==========================+==================================================================+================+=======================+==================================================+
| > Год появления          | > 1992                                                           | > 1995         | > 2002                | > 2008                                           |
+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+
| > Длина вывода           | > 128 бит                                                        | > 160 бит      | > 256/512 бит         | > 224/256/384/512 бит                            |
+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+
| > Хеш-конфликты          | > Много                                                          | > Много        | > Мало                | > Мало                                           |
+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+
| > Уровень без- опасности | > Низкий, есть из- вестные уязви- мости                          | > Низкий, есть | > Высокий             | > Высокий                                        |
|                          |                                                                  | >              |                       |                                                  |
|                          |                                                                  | > уязвимости   |                       |                                                  |
+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+
| > Применение             | > Устарел, но еще используется для проверки целост- ности данных | > Устарел      | > Проверка транзакций | > Может использовать- ся в качестве замены SHA-2 |
|                          |                                                                  |                | >                     |                                                  |
|                          |                                                                  |                | > в криптовалюте,     |                                                  |
|                          |                                                                  |                | >                     |                                                  |
|                          |                                                                  |                | > подписи и т. д.     |                                                  |
+--------------------------+------------------------------------------------------------------+----------------+-----------------------+--------------------------------------------------+

> известные
>
> цифровые

### Хеш-значения для структур данных

> Ключи в хеш-таблице могут быть представлены в виде целых чисел, дробей или строк. Языки программирования обычно предоставляют встроенные хеш- алгоритмы для своих типов данных, чтобы вычислять индексы корзин в хеш- таблице. Например, в Python можно вызвать функцию hash() для вычисления хеш-значений для различных типов данных.

- Хеш-значение целых чисел и булевых величин совпадает с их значением.

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

- Хеш-значение кортежа получается путем хеширования каждого элемен- та и объединения этих хеш-значений в одно.

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

> \# === File: built_in_hash.py ===
>
> num = 3
>
> hash_num = hash(num)
>
> \# Хеш-значение целого числа 3 равно 3.
>
> bol = True
>
> hash_bol = hash(bol)
>
> \# Хеш-значение булевой величины True равно 1.
>
> dec = 3.14159
>
> hash_dec = hash(dec)
>
> \# Хеш-значение дробного числа 3.14159 равно 326484311674566659.
>
> str = \"Hello 算法\"
>
> hash_str = hash(str)
>
> \# Хеш-значение строки \"Hello 算法\" равно 4617003410720528961.
>
> tup = (12836, \" 小哈\") hash_tup = hash(tup)
>
> \# Хеш-значение кортежа (12836, \'小哈\') равно 1029005403108185979.
>
> obj = ListNode(0) hash_obj = hash(obj)
>
> \# Хеш-значение объекта \<ListNode object at 0x1058fd810\> равно 274267521.
>
> Во многих языках программирования **только неизменяемые объекты могут использоваться в качестве ключей в хеш-таблице**. Если список (ди- намический массив) используется в качестве ключа, то при изменении его со- держимого хеш-значение также изменится, и мы не сможем найти исходное значение.
>
> Хотя переменные-члены пользовательских объектов (например, узлов связного списка) могут быть изменяемыми, сами объекты можно хеширо- вать. **Это связано с тем**, **что хеш-значение объекта обычно генериру- ется на основе его адреса в памяти**, и даже если содержимое объекта из- меняется, адрес остается неизменным, а значит, и хеш-значение также оста- ется прежним.
>
> Возможно, вы заметили, что при запуске программы в разных окнах выво- димые хеш-значения отличаются. **Это связано с тем, что интерпретатор Py- thon при каждом запуске добавляет случайное значение «соли» к функ- ции хеширования строк**. Такой подход эффективно предотвращает атаки типа HashDoS и повышает безопасность хеш-алгоритма.

#### резюме

##### Ключевые моменты

- При вводе ключа key хеш-таблица может найти значение value за время

> *O*(1), что очень эффективно.

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

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

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

  - Чем больше емкость хеш-таблицы, тем ниже вероятность хеш- конфликтов. Поэтому расширение хеш-таблицы может уменьшить ко- личество конфликтов, но, как и в случае с массивами, расширение хеш- таблицы требует значительных затрат.

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

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

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

  - Разные языки программирования реализуют хеш-таблицы по-разному. Например, класс HashMap в Java использует цепную адресацию, тогда как Dict в Python применяет метод открытой адресации.

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

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

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

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

##### Вопросы и ответы

> **Вопрос**. В каких случаях временная сложность хеш-таблицы составляет *O*(*n*)?
>
> **Ответ**. Когда хеш-коллизий становится достаточно много, временная слож- ность хеш-таблицы может ухудшиться до *O*(*n*). Если хеш-функция хорошо спроектирована, установлена разумная емкость, а коллизии распределены равномерно, временная сложность составляет *O*(1). При использовании встро- енных хеш-таблиц языков программирования обычно предполагается, что временная сложность составляет *O*(1).
>
> **Вопрос**. Почему бы не использовать хеш-функцию *f*(*x*) = *x*? Тогда не будет коллизий.
>
> **Ответ**. При использовании хеш-функции *f*(*x*) = *x* каждому элементу соот- ветствует уникальный индекс корзины, что эквивалентно массиву. Однако пространство входных данных обычно значительно больше пространства выходных данных (длины массива), поэтому последним этапом работы хеш- функции часто является взятие остатка от деления на длину массива. Други- ми словами, цель хеш-таблицы -- отобразить большее пространство состояний в меньшее пространство и обеспечить эффективность запросов *O*(1).
>
> **Вопрос**. Почему реализация хеш-таблицы на основе массива, связного спи- ска или двоичного дерева может быть более эффективной?
>
> **Ответ**. Во-первых, временная эффективность хеш-таблицы увеличивается, но пространственная эффективность уменьшается. Значительная часть памя- ти хеш-таблицы остается неиспользованной.
>
> Во-вторых, временная эффективность увеличивается только в определен- ных сценариях использования. Если функцию можно реализовать с использо- ванием массива или связного списка с той же временной сложностью, то это обычно быстрее, чем хеш-таблица. Это связано с тем, что вычисление хеш- функции требует затрат, а константа временной сложности больше.
>
> Наконец, временная сложность хеш-таблицы может ухудшиться. Например, при использовании цепной адресации поиск выполняется в связном списке или красно-черном дереве, что все еще может привести к ухудшению до времени *O*(*n*). **Вопрос**. Есть ли у метода множественного хеширования недостаток невоз- можности прямого удаления элементов? Можно ли повторно использовать
>
> пространство, помеченное как удаленное?
>
> **Ответ**. Множественное хеширование является одной из форм открытой адресации, и все методы открытой адресации имеют недостаток невозможно- сти прямого удаления элементов, что требует пометки удаленных элементов. Пространство, помеченное как удаленное, можно использовать повторно. Ког- да новый элемент вставляется в хеш-таблицу и хеш-функция находит пози- цию, помеченную как удаленная, эту позиция можно использовать для нового элемента. Это позволяет сохранить последовательность поиска в хеш-таблице неизменной и обеспечить эффективность использования пространства.
>
> **Вопрос**. Почему в линейном зондировании при поиске элемента возникают хеш-коллизии?
>
> **Ответ**. При поиске с помощью хеш-функции находится соответствующая корзина и пара ключ--значение. Если ключ не совпадает, это означает наличие хеш-коллизии. Поэтому метод линейного зондирования будет последователь- но искать с заранее заданным шагом, пока не найдет правильное значение ключа или не достигнет условия конца поиска.
>
> **Вопрос**. Почему расширение хеш-таблицы может уменьшить количество хеш-коллизий?
>
> **Ответ**. Последним шагом хеш-функции часто является взятие остатка от деления на длину массива *n*, чтобы выходное значение попадало в диапазон индексов массива. После расширения длина массива *n* изменяется, и соответ- ствующий индекс ключа также может измениться. Несколько ключей, которые ранее попадали в одну корзину, после расширения могут распределиться по нескольким корзинам, что снижает количество хеш-коллизий.
>
> Глава 7