6.4   Краткие итоги¶

1.   Основные моменты¶

• Передав key , мы можем получить value из хеш-таблицы за \(O(1)\) времени, поэтому она очень эффективна.
• К типичным операциям хеш-таблицы относятся поиск, добавление пары ключ-значение, удаление пары ключ-значение и обход хеш-таблицы.
• Хеш-функция отображает key в индекс массива, после чего можно обратиться к соответствующему бакету и получить value .
• Два разных key после хеш-функции могут дать один и тот же индекс массива, что приводит к ошибочному результату поиска; это явление называется хеш-коллизией.
• Чем больше емкость хеш-таблицы, тем ниже вероятность хеш-коллизий. Поэтому хеш-коллизии можно смягчать путем расширения хеш-таблицы. Как и у массива, операция расширения у хеш-таблицы очень затратна.
• Коэффициент загрузки определяется как отношение числа элементов в хеш-таблице к числу бакетов, отражает степень серьезности хеш-коллизий и часто используется как условие запуска расширения хеш-таблицы.
• Метод цепочек превращает одиночный элемент в связный список и хранит все конфликтующие элементы в одном списке. Однако слишком длинный список снижает эффективность поиска, поэтому его можно дополнительно преобразовать в красно-черное дерево.
• Открытая адресация обрабатывает хеш-коллизии за счет многократного пробирования. Линейное пробирование использует фиксированный шаг, его недостатки - невозможность прямого удаления элементов и склонность к кластеризации. Повторное хеширование использует несколько хеш-функций и по сравнению с линейным пробированием меньше подвержено кластеризации, но требует больше вычислений.
• Разные языки программирования выбирают разные стратегии реализации хеш-таблиц. Например, HashMap в Java использует метод цепочек, а Dict в Python - открытую адресацию.
• Для хеш-таблицы желательно, чтобы хеш-алгоритм был детерминированным, быстрым и обеспечивал равномерное распределение. В криптографии от него дополнительно требуют устойчивости к коллизиям и эффекта лавины.
• В качестве модуля хеш-алгоритмы обычно используют большое простое число, чтобы максимально обеспечить равномерность распределения хеш-значений и снизить число хеш-коллизий.
• К распространенным хеш-алгоритмам относятся MD5, SHA-1, SHA-2 и SHA-3. MD5 часто применяли для проверки целостности файлов, а SHA-2 широко используется в протоколах и приложениях, связанных с безопасностью.
• Языки программирования обычно предоставляют для типов данных встроенные хеш-алгоритмы, чтобы вычислять индексы бакетов в хеш-таблице. Как правило, хешируемыми могут быть только неизменяемые объекты.

2.   Q & A¶

Q: В каких случаях временная сложность хеш-таблицы становится \(O(n)\) ?

Когда хеш-коллизии становятся достаточно серьезными, временная сложность хеш-таблицы деградирует до \(O(n)\) . Если хеш-функция спроектирована хорошо, емкость выбрана разумно, а конфликты распределены достаточно равномерно, то временная сложность обычно считается \(O(1)\) . При использовании встроенной хеш-таблицы языка программирования мы, как правило, и принимаем ее за \(O(1)\) .

Q: Почему бы не использовать хеш-функцию \(f(x) = x\) ? Тогда ведь коллизий не будет.

При хеш-функции \(f(x) = x\) каждому элементу соответствует уникальный индекс бакета, и такая структура становится эквивалентна массиву. Однако входное пространство обычно намного больше выходного пространства (длины массива), поэтому последним шагом хеш-функции обычно выступает взятие по модулю длины массива. Иначе говоря, цель хеш-таблицы состоит в том, чтобы отобразить большее пространство состояний в меньшее пространство и при этом обеспечить \(O(1)\) поиска.

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

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

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

Наконец, временная сложность хеш-таблицы тоже может деградировать. Например, при методе цепочек мы все равно выполняем поиск в связном списке или красно-черном дереве, поэтому риск деградации до \(O(n)\) сохраняется.

Q: Есть ли у повторного хеширования недостаток "нельзя напрямую удалять элементы"? Можно ли повторно использовать место, помеченное как удаленное?

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

Q: Почему при линейном пробировании во время поиска элемента вообще возникает хеш-коллизия?

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

Q: Почему расширение хеш-таблицы помогает смягчать хеш-коллизии?

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

Q: Если нам нужен быстрый доступ, почему бы просто не использовать массив?

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

Оставляйте свои идеи, вопросы и предложения в комментариях