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

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

¶Основные принципы

Хеш-таблица с открытой адресацией представляет собой массив фиксированного размера \( m \), где каждая ячейка может хранить один элемент (или быть пустой/удалённой). Для вставки, поиска или удаления элемента вычисляется его хеш-значение \( h(key) \), которое определяет начальный индекс в массиве. Если ячейка с этим индексом занята другим элементом (коллизия), то применяется процедура зондирования — последовательный просмотр других ячеек в соответствии с некоторой функцией зондирования \( p(key, i) \), где \( i \) — номер попытки (0, 1, 2, …). Процесс продолжается, пока не будет найдена свободная ячейка (для вставки) или искомый элемент (для поиска).

¶Функция зондирования

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

• Линейное зондирование: \( p(key, i) = (h(key) + i) \mod m \). Простейший метод, при котором последовательно проверяются ячейки \( h(key), h(key)+1, h(key)+2, \dots \) по модулю \( m \). Недостаток — склонность к первичной кластеризации: длинные последовательности занятых ячеек образуются, что замедляет поиск.
• Квадратичное зондирование: \( p(key, i) = (h(key) + c_1 i + c_2 i^2) \mod m \), где \( c_1 \) и \( c_2 \) — константы. Позволяет уменьшить первичную кластеризацию, но может привести к вторичной кластеризации (если разные ключи имеют одинаковый начальный индекс).
• Двойное хеширование: \( p(key, i) = (h_1(key) + i \cdot h_2(key)) \mod m \), где \( h_1 \) и \( h_2 \) — две независимые хеш-функции. \( h_2(key) \) должна быть взаимно простой с \( m \) и не равна нулю. Этот метод даёт наилучшее распределение и минимизирует кластеризацию, но требует больше вычислительных ресурсов.

¶Операции

¶Вставка

Для вставки элемента с ключом \( key \) вычисляется начальный индекс \( h(key) \). Если ячейка свободна, элемент помещается туда. Если занята, последовательно проверяются ячейки в соответствии с функцией зондирования, пока не будет найдена пустая ячейка или ячейка с пометкой «удалён». Вставка выполняется в первую найденную свободную ячейку. Если таблица полностью заполнена, вставка невозможна (требуется увеличение размера таблицы — рехеширование).

¶Поиск

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

¶Удаление

Простое удаление элемента (замена ячейки на пустую) в открытой адресации недопустимо, так как это может разорвать цепочку зондирования и сделать недоступными другие элементы, вставленные после удалённого. Вместо этого ячейка помечается специальным значением «удалён» (или «ленивое удаление»). При вставке такая ячейка считается свободной, при поиске — занятой (зондирование продолжается). Для поддержания эффективности периодически выполняется рехеширование — перестройка таблицы с удалением всех помеченных ячеек.

¶Преимущества и недостатки

¶Преимущества

• Эффективность использования памяти: все элементы хранятся в одном массиве, нет накладных расходов на указатели (как в связных списках). Это особенно важно при работе с небольшими элементами (например, целыми числами).
• Локальность данных: элементы располагаются в памяти последовательно, что улучшает производительность за счёт кэширования процессора.
• Простота реализации: базовые алгоритмы (линейное зондирование) легко реализуются и не требуют сложных структур данных.

¶Недостатки

• Чувствительность к загруженности: при коэффициенте загрузки \( \alpha > 0.7 \) производительность резко падает из-за увеличения числа коллизий и длины цепочек зондирования. Для поддержания приемлемой скорости требуется рехеширование при достижении порога.
• Кластеризация: линейное и квадратичное зондирование подвержены кластеризации, что замедляет поиск.
• Ограничение на размер таблицы: таблица должна быть достаточно большой, чтобы избежать полного заполнения. Рехеширование — дорогостоящая операция.
• Сложность удаления: необходимость ленивого удаления и рехеширования усложняет реализацию по сравнению с методом цепочек.

¶Применение

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

• Встроенные системы и базы данных с ограниченной памятью: где каждый байт на счету.
• Кэши процессоров: например, в кэш-памяти L1/L2 часто применяется открытая адресация с линейным зондированием из-за её простоты и локальности.
• Реализации хеш-таблиц в языках программирования: например, в Python (словари) до версии 3.6 использовалась открытая адресация с квадратичным зондированием. В Java класс HashMap использует метод цепочек, но HashSet и LinkedHashMap могут применять открытую адресацию в некоторых реализациях.
• Символьные таблицы компиляторов: для хранения идентификаторов и ключевых слов.

¶Сравнение с методом цепочек

¶Интересные факты

• В 1953 году Ханс Петер Лун (Hans Peter Luhn) предложил идею открытой адресации для хеш-таблиц, но широкое распространение метод получил после работ Дональда Кнута (Donald Knuth) в 1960-х годах.
• В современных высокопроизводительных системах (например, в базах данных уровня Google) часто используются гибридные подходы, сочетающие открытую адресацию с кэшированием и оптимизациями под конкретные архитектуры процессоров.
• В российской вычислительной технике открытая адресация применялась в ранних версиях операционной системы Эльбрус (разработка Института точной механики и вычислительной техники имени С. А. Лебедева РАН) для реализации системных таблиц.

¶Источники

• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ» (3-е издание), глава 11 «Хеш-таблицы».
• Кнут Д. «Искусство программирования», том 3 «Сортировка и поиск», раздел 6.4.
• Sedgewick R., Wayne K. «Algorithms» (4th edition), глава 3.4 «Hash Tables».
• Статья «Open addressing» в англоязычной Википедии (версия от 2023 года).