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

Классическое хеширование - это схема в компьютерном программировании для разрешения хэш-коллизий значений хеш-функций в таблице с использованием открытой адресации . Он также хорошо подходит для реализации параллельной хеш-таблицы . Хеширование в классическом стиле было введено Морисом Херлихи , Ниром Шавитом и Мораном Цафриром в 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. ^ Херлихи, Морис; Шавит, Нир; Цафрир, Моран (2008). «Хеширование в классическом стиле» (PDF) . DISC '08: Материалы 22-го международного симпозиума по распределенным вычислениям . Аркашон, Франция: Springer-Verlag. С. 350–364.

Внешние ссылки [ править ]