Открытая адресация
Открытая адресация или закрытое хеширование — это метод разрешения коллизий в хэш-таблицах . С помощью этого метода коллизия хэшей разрешается путем зондирования или поиска альтернативных мест в массиве ( пробная последовательность ) до тех пор, пока не будет найдена целевая запись или не будет найден неиспользуемый слот массива, что указывает на отсутствие такого ключа в массиве. стол. [1] Хорошо известные последовательности зондов включают:
- Линейное зондирование
- в котором интервал между зондами фиксирован — часто устанавливается равным 1.
- Квадратичное зондирование
- при котором интервал между зондами увеличивается квадратично (следовательно, индексы описываются квадратичной функцией).
- Двойное хеширование
- в котором интервал между проверками фиксирован для каждой записи, но вычисляется другой хэш-функцией.
Основные недостатки между этими методами заключаются в том, что линейное зондирование имеет лучшую производительность кэша , но наиболее чувствительно к кластеризации , тогда как двойное хеширование имеет низкую производительность кэша, но практически не демонстрирует кластеризации; квадратичное зондирование занимает промежуточное положение в обеих областях. Двойное хеширование также может потребовать больше вычислений, чем другие формы зондирования.
Некоторые методы открытой адресации, такие как Классическое хеширование , Робин Гуд перемешивает , Хеширование по принципу «последний пришел первым» и хеширование «кукушка» перемещают существующие ключи в массиве, чтобы освободить место для нового ключа. Это дает лучшее максимальное время поиска, чем методы, основанные на зондировании. [2] [3] [4] [5] [6]
Критическое влияние на производительность хэш-таблицы с открытой адресацией оказывает коэффициент загрузки ; то есть доля используемых слотов в массиве. Когда коэффициент загрузки увеличивается до 100 %, количество зондов, которые могут потребоваться для поиска или вставки данного ключа, резко возрастает. Как только таблица заполнится, алгоритмы проверки могут даже не завершиться. Даже при наличии хороших хэш-функций коэффициент загрузки обычно ограничивается 80%. Плохая хеш-функция может демонстрировать плохую производительность даже при очень низких коэффициентах нагрузки из-за значительной кластеризации, особенно при использовании простейшего метода линейной адресации. Обычно типичные коэффициенты загрузки для большинства методов открытой адресации составляют 50 %, тогда как для отдельных цепочек обычно может использоваться до 100 %.
Пример псевдокода
[ редактировать ]Следующий псевдокод представляет собой реализацию хеш-таблицы открытой адресации с линейным зондированием и однослотовым степпингом — распространенный подход, который эффективен, если хеш-функция хорошая. Каждая из функций поиска , установки и удаления использует общую внутреннюю функцию find_slot для поиска слота массива, который либо содержит, либо должен содержать заданный ключ.
record pair { key, value, occupied flag (initially unset) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]
function find_slot(key)
i := hash(key) modulo num_slots
// search until we either find the key, or find an empty slot.
while (slot[i] is occupied) and (slot[i].key ≠ key)
i := (i + 1) modulo num_slots
return i
function lookup(key)
i := find_slot(key)
if slot[i] is occupied // key is in table
return slot[i].value
else // key is not in table
return not found
function set(key, value)
i := find_slot(key)
if slot[i] is occupied // we found our key
slot[i].value := value
return
if the table is almost full
rebuild the table larger (note 1)
i := find_slot(key)
mark slot[i] as occupied
slot[i].key := key
slot[i].value := value
- примечание 1
- Для восстановления таблицы необходимо выделить больший массив и рекурсивно использовать операцию set для вставки всех элементов старого массива в новый больший массив. Обычно размер массива увеличивают экспоненциально , например, удваивая старый размер массива.
function remove(key)
i := find_slot(key)
if slot[i] is unoccupied
return // key is not in the table
mark slot[i] as unoccupied
j := i
loop (note 2)
j := (j + 1) modulo num_slots
if slot[j] is unoccupied
exit loop
k := hash(slot[j].key) modulo num_slots
// determine if k lies cyclically in (i,j]
// i ≤ j: | i..k..j |
// i > j: |.k..j i....| or |....j i..k.|
if i ≤ j
if (i < k) and (k ≤ j)
continue loop
else
if (k ≤ j) or (i < k)
continue loop
mark slot[i] as occupied
slot[i].key := slot[j].key
slot[i].value := slot[j].value
mark slot[j] as unoccupied
i := 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 г.