Хеширование в классическом стиле - Hopscotch hashing

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

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

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

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

Вот как добавить товар Икс который был хеширован в ведро я:

  1. Если информационное слово перехода для ведра я шоу уже есть ЧАС предметы в этом ведре, стол заполнен; разверните хеш-таблицу и попробуйте еще раз.
  2. Начиная с входа я, используйте линейный зонд, чтобы найти пустую запись по индексу j. (Если пустого слота нет, таблица заполнена.)
  3. В то время как (j−я) мод п ≥ ЧАС, переместите пустой слот в сторону я следующим образом:
    1. Искать ЧАС−1 слота, предшествующего j для предмета y чье хеш-значение k внутри ЧАС−1 из j, т.е. (j−k) мод п < ЧАС. (Это можно сделать с помощью слов информации о переходе.)
    2. Если такого предмета нет y существует в пределах диапазона, таблица заполнена.
    3. Шаг y к j, создавая новый пустой слот ближе к я.
    4. Набор j в пустую ячейку, освобожденную y и повторить.
  4. хранить Икс в слоте j и вернуться.

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

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

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

Смотрите также

использованная литература

  1. ^ Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). "Хеширование в классиках" (PDF). DISC '08: Материалы 22-го международного симпозиума по распределенным вычислениям. Аркашон, Франция: Springer-Verlag. С. 350–364.

внешние ссылки