Классическое хеширование
Хопскотч-хеширование — это схема в компьютерном программировании для разрешения хеш-коллизий значений хеш-функций в таблице с использованием открытой адресации . Он также хорошо подходит для реализации параллельной хеш-таблицы . Хеширование Hopscotch было представлено Морисом Херлихи , Ниром Шавитом и Мораном Цафриром в 2008 году. [1] Название происходит от последовательности прыжков, которая характеризует алгоритм вставки таблицы (см. « Игры для детей»).
Алгоритм использует один массив из n сегментов. Для каждого сегмента его окрестность представляет собой небольшой набор H последовательных сегментов (т. е. с индексами, близкими к исходному хешированному блоку). Желаемое свойство окрестности состоит в том, чтобы стоимость поиска элемента в корзинах окрестности была близка к стоимости поиска его в самой корзине (например, если корзины соседства попадают в одну и ту же строку кэша ). Размер окрестности должен быть достаточным для размещения логарифмического числа элементов в худшем случае (т. е. он должен вмещать log( n ) элементов), но в среднем только постоянного числа. Если какая-либо область сегмента заполнена, размер таблицы изменяется.
При хешировании в классиках, как и при хешировании с кукушкой , и в отличие от линейного зондирования , данный элемент всегда будет вставлен и найден поблизости от его хешированной корзины. Другими словами, он всегда будет найден либо в исходной записи хеш-массива, либо в одной из следующих H -1 соседних записей. H Например, может быть равно 32 — обычному размеру машинного слова. Таким образом, окрестность представляет собой «виртуальный» блок, имеющий фиксированный размер и перекрывающийся со следующими блоками H -1. Для ускорения поиска каждая корзина (запись массива) включает в себя слово «информации о переходе», H -битное растровое изображение, которое указывает, какая из следующих записей H -1 содержит элементы, хэшированные с виртуальным сегментом текущей записи. Таким образом, элемент можно быстро найти, посмотрев на слово, чтобы увидеть, какие записи принадлежат сегменту, а затем просканировав постоянное количество записей (большинство современных процессоров поддерживают специальные операции манипуляции с битами, которые выполняют поиск в «прыжке»). -информация» растровое изображение очень быстро).
Вот как добавить элемент x , который был хеширован в корзину i :
- Если слово информации о переходе для сегмента i показывает, что в этом сегменте уже есть H элементов, таблица заполнена; разверните хеш-таблицу и повторите попытку.
- Начиная с записи i , используйте линейный зонд, чтобы найти пустую запись с индексом j . (Если пустого места нет, таблица заполнена.)
- Пока ( j − i ) mod n ≥ H , переместите пустой слот в сторону i следующим образом:
- Найдите в слотах H -1, предшествующих j , элемент y , хеш-значение которого k находится в пределах H -1 от j , т.е. ( j - k mod n < H. ) (Это можно сделать, используя слова, передающие информацию о прыжке.)
- Если такого элемента y в диапазоне не существует, таблица заполнена.
- Переместите y в j , создав новый пустой слот ближе к i .
- Установите j в пустой слот, освобожденный y , и повторите.
- Сохраните x в слоте j и вернитесь.
Идея состоит в том, что хеширование в классиках «перемещает пустой слот в сторону желаемого ведра». Это отличает его от линейного зондирования , при котором остается пустой слот, в котором он был найден, возможно, далеко от исходного сегмента, или от хеширования с кукушкой , которое для создания свободного сегмента перемещает элемент из одного из желаемых сегментов в целевые массивы, и только потом пытается найти смещенный элемент на новом месте.
Чтобы удалить элемент из таблицы, его просто удаляют из записи таблицы. Если сегменты соседства выровнены по кешу, то можно применить операцию реорганизации, при которой элементы перемещаются в теперь свободное место, чтобы улучшить выравнивание.
Одним из преимуществ хеширования в классиках является то, что оно обеспечивает хорошую производительность при очень высоких коэффициентах загрузки таблицы, даже превышающих 0,9. Частично эта эффективность обусловлена использованием линейного зондирования только для поиска пустого слота во время вставки, а не для каждого поиска, как в исходном алгоритме хэш-таблицы линейного зондирования . Еще одним преимуществом является то, что можно использовать любую хеш-функцию, в частности простые, близкие к универсальным.
Варианты
[ редактировать ]В статье также представлены несколько вариантов схемы хеширования в классах. [1]
Расширенный подход использует схему указателей для реализации слова информации о переходе (в базовом случае это битовая карта информации о переходе ). Это позволяет информационному слову перехода иметь произвольный (но фиксированный) размер.
Хотя базовый вариант и расширенный подход разработаны как последовательные также существует параллельный , для каждого из них вариант.
Вариант без блокировки был представлен Робертом Келли, Бараком А. Перлмуттером и Филом Магуайром в 2020 году. [2]
См. также
[ редактировать ]- Хеширование с кукушкой
- Хэш-столкновение
- Хэш-функция
- Линейное зондирование
- Открытая адресация
- Идеальное хеширование
- Квадратичное зондирование
- Классики
Ссылки
[ редактировать ]- ↑ Перейти обратно: Перейти обратно: а б Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). «Хеширование в классиках» (PDF) . DISC '08: Материалы 22-го международного симпозиума по распределенным вычислениям . Аркашон, Франция: Springer-Verlag. стр. 350–364. Архивировано из оригинала (PDF) 20 декабря 2022 г.
- ^ Келли, Роберт; Перлмуттер, Барак А.; Магуайр, Фил (2020). «Безблокировочное хеширование в классиках» . Симпозиум по алгоритмическим принципам компьютерных систем (APOCS) : 45–59. doi : 10.1137/1.9781611976021 – через SIAM.
Внешние ссылки
[ редактировать ]- libhhash — реализация хеширования в стиле C
- hopscotch-map — реализация хэш-карты на C++ с использованием хеширования в классах.
- Гуссерт, Эммануэль (11 августа 2013 г.). «Хеширование в классиках» . Проверено 16 октября 2019 г. Подробное описание и пример реализации.