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

Конфликт хэша разрешен линейным зондированием (интервал = 1).

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

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

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

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

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

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

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

записывать пара {ключ, значение}вар парный массив слот [0..num_slots-1]
функция find_slot (ключ) i: = hash (key) по модулю num_slots // ищем, пока не найдем ключ или не найдем пустой слот.    пока (слот [i] занят) и (слот [i] .key ≠ ключ) i = (i + 1) по модулю num_slots возвращаться я
функция поиск (ключ) i: = find_slot (ключ) если слот [i] занят // ключ находится в таблице        возвращаться слот [i]. значение еще                     // ключа нет в таблице        возвращаться не найден
функция set (ключ, значение) i: = find_slot (ключ) если слот [i] занят // мы нашли наш ключ        слот [i] .value = значение возвращаться    если стол почти заполнен перестроить стол больше (примечание 1)        i = find_slot (key) slot [i] .key = ключевой слот [i] .value = значение
примечание 1
Перестройка таблицы требует выделения большего массива и рекурсивного использования набор операция для вставки всех элементов старого массива в новый больший массив. Обычно увеличивают размер массива экспоненциально, например, удвоив размер старого массива.
функция удалить (ключ) i: = find_slot (ключ) если слот [i] не занят возврат // ключа нет в таблице    j: = я петля        отметить слот [i] как незанятый r2: (заметка 2)        j: = (j + 1) по модулю num_slots если слот [j] не занят цикл выхода        k: = hash (slot [j] .key) modulo num_slots // определить, лежит ли k циклически в (i, j] // | ikj | // | .... j ik | или | .k..j i ... | если ((i <= j)? ((i 
заметка 2
Для всех записей в кластере не должно быть свободных слотов между их естественной хэш-позицией и их текущей позицией (иначе поиск будет завершен до нахождения записи). На этом этапе псевдокода я - это свободный слот, который может сделать это свойство недействительным для последующих записей в кластере. j вот такая последующая запись. k это необработанный хеш, где запись в j естественно попал бы в хеш-таблицу, если бы не было коллизий. Этот тест спрашивает, есть ли запись в j неверно позиционируется относительно требуемых свойств кластера теперь, когда я вакантно.
Другой способ удаления - просто пометить слот как удаленный. Однако это в конечном итоге требует перестройки таблицы просто для удаления удаленных записей. Приведенные выше методы обеспечивают О(1) обновление и удаление существующих записей с периодической перестройкой, если максимальная отметка размера таблицы увеличивается.
В О(1) метод удаления, описанный выше, возможен только в хеш-таблицах с линейным зондированием и пошаговым выполнением одного слота. В случае, когда необходимо удалить много записей за одну операцию, отметка слотов для удаления и последующее восстановление может быть более эффективным.
Смотрите также












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












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