Jump to content

Классическое хеширование

Классическое перемешивание. Здесь H равно 4. Серые записи заняты. В части (a) элемент x добавляется с хеш-значением 6. Линейный зонд обнаруживает, что запись 13 пуста. Поскольку 13 находится на расстоянии более 4 записей от 6, алгоритм ищет более раннюю запись для замены на 13. Первое место для поиска - это H -1 = 3 записи раньше, в записи 10. Битовая карта информации о переходе этой записи указывает что d , элемент в записи 11, может быть смещен на 13. После перемещения d , запись 11 все еще находится слишком далеко от записи 6, поэтому алгоритм проверяет запись 8. Битовая карта информации о переходе указывает, что элемент c в записи 9 может быть перемещено в запись 11. Наконец, a перемещается в запись 9. Часть (b) показывает состояние таблицы непосредственно перед добавлением x .

Хопскотч-хеширование — это схема в компьютерном программировании для разрешения хеш-коллизий значений хеш-функций в таблице с использованием открытой адресации . Он также хорошо подходит для реализации параллельной хеш-таблицы . Хеширование Hopscotch было представлено Морисом Херлихи , Ниром Шавитом и Мораном Цафриром в 2008 году. [1] Название происходит от последовательности прыжков, которая характеризует алгоритм вставки таблицы (см. « Игры для детей»).

Алгоритм использует один массив из n сегментов. Для каждого сегмента его окрестность представляет собой небольшой набор H последовательных сегментов (т. е. с индексами, близкими к исходному хешированному блоку). Желаемое свойство окрестности состоит в том, чтобы стоимость поиска элемента в корзинах окрестности была близка к стоимости поиска его в самой корзине (например, если корзины соседства попадают в одну и ту же строку кэша ). Размер окрестности должен быть достаточным для размещения логарифмического числа элементов в худшем случае (т. е. он должен вмещать log( n ) элементов), но в среднем только постоянного числа. Если какая-либо область сегмента заполнена, размер таблицы изменяется.

При хешировании в классиках, как и при хешировании с кукушкой , и в отличие от линейного зондирования , данный элемент всегда будет вставлен и найден поблизости от его хешированной корзины. Другими словами, он всегда будет найден либо в исходной записи хеш-массива, либо в одной из следующих H -1 соседних записей. H Например, может быть равно 32 — обычному размеру машинного слова. Таким образом, окрестность представляет собой «виртуальный» блок, имеющий фиксированный размер и перекрывающийся со следующими блоками H -1. Для ускорения поиска каждая корзина (запись массива) включает в себя слово «информации о переходе», H -битное растровое изображение, которое указывает, какая из следующих записей H -1 содержит элементы, хэшированные с виртуальным сегментом текущей записи. Таким образом, элемент можно быстро найти, посмотрев на слово, чтобы увидеть, какие записи принадлежат сегменту, а затем просканировав постоянное количество записей (большинство современных процессоров поддерживают специальные операции манипуляции с битами, которые выполняют поиск в «прыжке»). -информация» растровое изображение очень быстро).

Вот как добавить элемент x , который был хеширован в корзину i :

  1. Если слово информации о переходе для сегмента i показывает, что в этом сегменте уже есть H элементов, таблица заполнена; разверните хеш-таблицу и повторите попытку.
  2. Начиная с записи i , используйте линейный зонд, чтобы найти пустую запись с индексом j . (Если пустого места нет, таблица заполнена.)
  3. Пока ( j i ) mod n H , переместите пустой слот в сторону i следующим образом:
    1. Найдите в слотах H -1, предшествующих j , элемент y , хеш-значение которого k находится в пределах H -1 от j , т.е. ( j - k mod n < H. ) (Это можно сделать, используя слова, передающие информацию о прыжке.)
    2. Если такого элемента y в диапазоне не существует, таблица заполнена.
    3. Переместите y в j , создав новый пустой слот ближе к i .
    4. Установите j в пустой слот, освобожденный y , и повторите.
  4. Сохраните x в слоте j и вернитесь.

Идея состоит в том, что хеширование в классиках «перемещает пустой слот в сторону желаемого ведра». Это отличает его от линейного зондирования , при котором остается пустой слот, в котором он был найден, возможно, далеко от исходного сегмента, или от хеширования с кукушкой , которое для создания свободного сегмента перемещает элемент из одного из желаемых сегментов в целевые массивы, и только потом пытается найти смещенный элемент на новом месте.

Чтобы удалить элемент из таблицы, его просто удаляют из записи таблицы. Если сегменты соседства выровнены по кешу, то можно применить операцию реорганизации, при которой элементы перемещаются в теперь свободное место, чтобы улучшить выравнивание.

Одним из преимуществ хеширования в классиках является то, что оно обеспечивает хорошую производительность при очень высоких коэффициентах загрузки таблицы, даже превышающих 0,9. Частично эта эффективность обусловлена ​​использованием линейного зондирования только для поиска пустого слота во время вставки, а не для каждого поиска, как в исходном алгоритме хэш-таблицы линейного зондирования . Еще одним преимуществом является то, что можно использовать любую хеш-функцию, в частности простые, близкие к универсальным.

Варианты

[ редактировать ]

В статье также представлены несколько вариантов схемы хеширования в классах. [1]

Расширенный подход использует схему указателей для реализации слова информации о переходе (в базовом случае это битовая карта информации о переходе ). Это позволяет информационному слову перехода иметь произвольный (но фиксированный) размер.

Хотя базовый вариант и расширенный подход разработаны как последовательные также существует параллельный , для каждого из них вариант.

Вариант без блокировки был представлен Робертом Келли, Бараком А. Перлмуттером и Филом Магуайром в 2020 году. [2]

См. также

[ редактировать ]
  1. Перейти обратно: Перейти обратно: а б Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). «Хеширование в классиках» (PDF) . DISC '08: Материалы 22-го международного симпозиума по распределенным вычислениям . Аркашон, Франция: Springer-Verlag. стр. 350–364. Архивировано из оригинала (PDF) 20 декабря 2022 г.
  2. ^ Келли, Роберт; Перлмуттер, Барак А.; Магуайр, Фил (2020). «Безблокировочное хеширование в классиках» . Симпозиум по алгоритмическим принципам компьютерных систем (APOCS) : 45–59. doi : 10.1137/1.9781611976021 – через SIAM.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: be40ef3c4aaade60ca0d1e690bb98a7b__1717237200
URL1:https://arc.ask3.ru/arc/aa/be/7b/be40ef3c4aaade60ca0d1e690bb98a7b.html
Заголовок, (Title) документа по адресу, URL1:
Hopscotch hashing - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)