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

# Резюме

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

- При вводе `key` хеш-таблица может найти `value` за время $O(1)$, что очень эффективно.
- К основным операциям с хеш-таблицами относятся поиск, добавление пар ключ-значение, удаление пар ключ-значение и обход хеш-таблицы.
- Хеш-функция отображает `key` в индекс массива, что позволяет получить доступ к соответствующей корзине и получить `value`.
- Два различных `key` могут после применения хеш-функции получить одинаковый индекс массива, что приводит к ошибкам в результатах запросов. Это явление называется хеш-коллизией.
- Чем больше емкость хеш-таблицы, тем ниже вероятность хеш-коллизий. Поэтому можно уменьшить хеш-коллизии путем увеличения емкости хеш-таблицы. Подобно увеличению емкости массива, операция увеличения емкости хеш-таблицы требует больших затрат.
- Коэффициент заполнения определяется как количество элементов в хеш-таблице, деленное на количество корзин, и отражает степень серьезности хеш-коллизий. Часто используется как условие для увеличения емкости хеш-таблицы.
- Цепная адресация преобразует отдельный элемент в связный список, храня все конфликтующие элементы в одном списке. Однако слишком длинные списки снижают эффективность поиска, что можно улучшить путем дальнейшего преобразования списка в красно-черное дерево.
- Открытая адресация обрабатывает хеш-коллизии с помощью многократного зондирования. Линейное зондирование использует фиксированный шаг, но имеет недостаток в том, что элементы нельзя удалять, и легко возникает кластеризация. Множественное хеширование использует несколько хеш-функций для зондирования, что по сравнению с линейным зондированием менее склонно к кластеризации, но несколько хеш-функций увеличивают объем вычислений.
- Различные языки программирования используют разные реализации хеш-таблиц. Например, `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)$.

**В**: Имеет ли множественное хеширование недостаток невозможности прямого удаления элементов? Может ли пространство, помеченное как удаленное, быть использовано повторно?

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

**В**: Почему при линейном зондировании возникают хеш-коллизии при поиске элемента?

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

**В**: Почему увеличение емкости хеш-таблицы может уменьшить хеш-коллизии?

Последний шаг хеш-функции часто заключается в взятии остатка от деления на длину массива $n$ (взятие остатка), чтобы выходное значение попало в диапазон индексов массива; после увеличения емкости длина массива $n$ изменяется, и индекс, соответствующий `key`, также может измениться. Несколько `key`, которые ранее попадали в одну корзину, после увеличения емкости могут быть распределены в несколько корзин, что уменьшает хеш-коллизии.

**В**: Если нужна эффективная запись и чтение, то почему бы не использовать просто массив?

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