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 в индекс массива, а затем использовать массив корзин для хранения элементов. Такая структура и есть хеш-таблица.