Открытая адресация или закрытое хеширование — это метод разрешения коллизий в хеш-таблицах . С помощью этого метода коллизия хеш-таблиц разрешается путем зондирования или поиска по альтернативным позициям в массиве ( последовательность зондирования ) до тех пор, пока не будет найдена целевая запись или неиспользуемый слот массива, что указывает на отсутствие такого ключа в таблице. [1] Известные последовательности зондирования включают в себя:
Основные компромиссы между этими методами заключаются в том, что линейное зондирование имеет лучшую производительность кэша , но наиболее чувствительно к кластеризации , в то время как двойное хеширование имеет плохую производительность кэша, но практически не демонстрирует кластеризации; квадратичное зондирование находится посередине в обеих областях. Двойное хеширование также может потребовать больше вычислений, чем другие формы зондирования.
Некоторые методы открытой адресации, такие как хеширование Hopscotch , хеширование Robin Hood , хеширование last-come-first-served и хеширование cuckoo, перемещают существующие ключи в массиве, чтобы освободить место для нового ключа. Это дает лучшее максимальное время поиска, чем методы, основанные на зондировании. [2] [3] [4] [5] [6]
Критическое влияние на производительность хэш-таблицы с открытой адресацией оказывает фактор загрузки , то есть доля используемых слотов в массиве. По мере того, как фактор загрузки приближается к 100%, количество зондов, которые могут потребоваться для поиска или вставки заданного ключа, резко возрастает. Как только таблица заполняется, алгоритмы зондирования могут даже не завершиться. Даже с хорошими хэш-функциями факторы загрузки обычно ограничены 80%. Плохая хэш-функция может демонстрировать низкую производительность даже при очень низких факторах загрузки, создавая значительную кластеризацию, особенно с простейшим методом линейной адресации. Обычно типичные факторы загрузки с большинством методов открытой адресации составляют 50%, в то время как раздельное связывание обычно может использовать до 100%.
Следующий псевдокод представляет собой реализацию хэш-таблицы с открытой адресацией с линейным зондированием и однослотовым шагом, распространенный подход, который эффективен, если хэш-функция хороша. Каждая из функций lookup , set и remove использует общую внутреннюю функцию find_slot для поиска слота массива, который либо содержит, либо должен содержать заданный ключ.
запись пара { ключ, значение, занятый флаг (изначально не установлен) } var пара слот[0], слот[1], ..., слот[num_slots - 1]функция find_slot(ключ) i := hash(key) по модулю num_slots // ищем, пока не найдем ключ или пустой слот. while (slot[i] занят) and (slot[i].key ≠ key) i := (i + 1) по модулю num_slots вернуть я
функция поиска(ключ) я := find_slot(ключ) если слот[i] занят // ключ есть в таблице return слот[i].значение else // ключ отсутствует в таблице return не найден
функция set(ключ, значение) я := find_slot(ключ) если слот[i] занят // мы нашли наш ключ слот[i].значение := значение вернуться , если таблица почти заполнена перестроить таблицу большего размера (примечание 1) я := find_slot(ключ) отметить слот[i] как занятый слот[i].ключ := ключ слот[i].значение := значение
функция удалить(ключ) я := find_slot(ключ) если слот[i] не занят, вернуть // ключ отсутствует в таблице пометить слот[i] как незанятый j := я петля (примечание 2) j := (j + 1) по модулю num_slots если слот[j] не занят, выйти из цикла k := hash(slot[j].key) по модулю num_slots // определить, лежит ли k циклически в (i,j] // i ≤ j: | i..k..j | // i > j: |.k..j i....| или |....j i..k.| если i ≤ j если (i < k) и (k ≤ j) продолжить цикл иначе если (k ≤ j) или (i < k) продолжить цикл отметить слот[i] как занятый слот[i].ключ := слот[j].ключ слот[i].значение := слот[j].значение пометить слот[j] как незанятый я := j
Другой метод удаления — просто пометить слот как удаленный. Однако это в конечном итоге требует перестроения таблицы просто для удаления удаленных записей. Методы выше обеспечивают обновление и удаление существующих записей O (1) с периодическим перестроением, если высшая точка размера таблицы растет.
Метод удаления O (1) выше возможен только в линейно зондируемых хэш-таблицах с однослотовым шагом. В случае, когда необходимо удалить много записей за одну операцию, маркировка слотов для удаления и последующего перестроения может быть более эффективной.