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

Коллизия хешей разрешена путем линейного зондирования (интервал = 1).

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

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

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

Некоторые методы открытой адресации, такие как Классическое хеширование , Робин Гуд перемешивает , Хеширование в порядке очереди и хеширование с кукушкой перемещают существующие ключи в массиве, чтобы освободить место для нового ключа. Это дает лучшее максимальное время поиска, чем методы, основанные на зондировании. ^[2]^[3]^[4]^[5]^[6]

Критическое влияние на производительность хеш-таблицы открытой адресации оказывает коэффициент загрузки ; то есть доля используемых слотов в массиве. Когда коэффициент загрузки увеличивается до 100 %, количество зондов, которые могут потребоваться для поиска или вставки данного ключа, резко возрастает. Как только таблица заполнится, алгоритмы проверки могут даже не завершиться. Даже при наличии хороших хэш-функций коэффициент загрузки обычно ограничивается 80%. Плохая хэш-функция может демонстрировать плохую производительность даже при очень низких коэффициентах нагрузки из-за значительной кластеризации, особенно при использовании простейшего метода линейной адресации. Обычно типичные коэффициенты загрузки для большинства методов открытой адресации составляют 50 %, тогда как при раздельном связывании обычно может использоваться до 100 %.

Пример псевдокода

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

пара записей  {ключ, значение, флаг занятости (изначально не установлен) } пара  переменных slot[0], slot[1], ..., slot[num_slots - 1]

функция  find_slot (ключ)    я := хеш(ключ) по модулю num_slots     // ищем, пока либо не найдём ключ, либо не найдём пустой слот.      while  (slot[i] занят) и (slot[i].key ≠ key)        я := (я + 1) по модулю num_slots     вернуть  я

поиск функции  (ключ)    я := find_slot(ключ)     если  слот[i] занят  // ключ находится в таблице,          возвращаем  slot[i].value     else                       // ключа нет в таблице,          return  не найден

набор функций  (ключ, значение)    я := find_slot(ключ)     если  слот[i] занят  // мы нашли наш ключ         слот[i].значение := значение         вернуться      , если  таблица почти заполнена        перестроить таблицу большего размера  (примечание 1)         я := find_slot(ключ)    пометить слот[i] как занятый    слот[i].key := ключ    слот[i].значение := значение

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

функция  удаления (ключ)    я := find_slot(ключ)     если  слот[i] не занят         return     // ключа нет в таблице     пометить слот[i] как незанятый    j := я     петля   (примечание 2)         j := (j + 1) по модулю num_slots         если  слот[j] не занят             выход из цикла         k := хэш(слот[j].key) по модулю num_slots         // определяем, лежит ли k циклически в (i,j]          // i ≤ j: | i..k..j |          // i > j: |.k..j i....| или |.. ..j i..k.|          если  я ≤ j             если  (i < k) и (k ≤ j)                 продолжить цикл          else              if  (k ≤ j) или (i < k)                 продолжить цикл         пометить слот[i] как занятый        слот[i].key := слот[j].key        слот[i].значение := слот[j].значение        пометить слот[j] как незанятый        я := j

примечание 2: Для всех записей в кластере не должно быть свободных мест между их естественной хэш-позицией и текущей позицией (иначе поиск прекратится до того, как будет найдена запись). На этом этапе псевдокода i — это свободный слот, который может сделать это свойство недействительным для последующих записей в кластере. j — такая последующая запись. k — это необработанный хэш, в котором запись с номером j естественным образом попала бы в хеш-таблицу, если бы не было коллизий. Этот тест проверяет, не позиционирована ли запись в j неверно относительно требуемых свойств кластера теперь, когда i вакантен.

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

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

См. также

Ленивое удаление – метод удаления из хеш-таблицы с использованием открытой адресации.

Ссылки

^ Тененбаум, Аарон М.; Лангсам, Едидия; Огенштейн, Моше Дж. (1990), Структуры данных с использованием C , Prentice Hall, стр. 456–461, стр. 472, ISBN 0-13-199746-7
^ Поблете; Виола; Манро.«Анализ схемы хеширования с помощью диагонального преобразования Пуассона».п. 95 изЯн ван Леувен (ред.) «Алгоритмы – ЕСА '94» .1994.
^ Стив Хеллер. «Эффективное программирование на C/C++: меньше, быстрее, лучше» 2014.п. 33.
^ Патрисио В. Поблете, Альфредо Виола. «Хеширование Робин Гуда действительно имеет постоянную среднюю стоимость поиска и дисперсию в полных таблицах» .2016.
^ Пол Э. Блэк, «Хеширование в порядке очереди» , в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 17 сентября 2015 г.
^ Пол Э. Блэк, «Хеширование Робин Гуда» , в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 17 сентября 2015 г.

[tenenbaum90-1] Тененбаум, Аарон М.; Лангсам, Едидия; Огенштейн, Моше Дж. (1990), Структуры данных с использованием C , Prentice Hall, стр. 456–461, стр. 472, ISBN 0-13-199746-7

[2] Поблете; Виола; Манро.«Анализ схемы хеширования с помощью диагонального преобразования Пуассона».п. 95 изЯн ван Леувен (ред.) «Алгоритмы – ЕСА '94» .1994.

[3] Стив Хеллер. «Эффективное программирование на C/C++: меньше, быстрее, лучше» 2014.п. 33.

[4] Патрисио В. Поблете, Альфредо Виола. «Хеширование Робин Гуда действительно имеет постоянную среднюю стоимость поиска и дисперсию в полных таблицах» .2016.

[5] Пол Э. Блэк, «Хеширование в порядке очереди» , в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 17 сентября 2015 г.

[6] Пол Э. Блэк, «Хеширование Робин Гуда» , в Словаре алгоритмов и структур данных [онлайн], Вреда Питерс и Пол Э. Блэк, ред. 17 сентября 2015 г.

[1]

[2]

[3]

[4]

[5]

[6]