Хеширование по методу «классики» — это схема в компьютерном программировании для разрешения коллизий хэшей значений хэш-функций в таблице с использованием открытой адресации . Она также хорошо подходит для реализации параллельной хэш-таблицы . Хеширование по методу «классики» было введено Морисом Херлихи , Ниром Шавитом и Мораном Цафриром в 2008 году. [1] Название происходит от последовательности скачков, которые характеризуют алгоритм вставки таблицы (см. игру «классики» для детей).
Алгоритм использует один массив из n блоков. Для каждого блока его окрестность представляет собой небольшую коллекцию из H последовательных блоков (т. е. тех, индексы которых близки к исходному хэшированному блоку). Желаемое свойство блока заключается в том, что стоимость поиска элемента в блоках блока близка к стоимости поиска его в самом блоке (например, если блоки в блоке попадают в одну и ту же строку кэша ). Размер блока должен быть достаточным для размещения логарифмического числа элементов в худшем случае (т. е. он должен вмещать log( n ) элементов), но только постоянное число в среднем. Если некоторое блоковое соседство заполнено, таблица изменяет размер.
В хешировании классиков, как и в хешировании кукушки , и в отличие от линейного зондирования , заданный элемент всегда будет вставлен и найден в окрестности его хешированного контейнера. Другими словами, он всегда будет найден либо в его исходной записи хешированного массива, либо в одной из следующих H −1 соседних записей. H может, например, быть 32, общим размером машинного слова. Таким образом, соседство является «виртуальным» контейнером, который имеет фиксированный размер и перекрывается со следующими H −1 контейнерами. Для ускорения поиска каждый контейнер (элемент массива) включает слово «информации о переходе», битовую карту H , которая указывает, какие из следующих H −1 записей содержат элементы, которые хэшируются в виртуальный контейнер текущей записи. Таким образом, элемент можно быстро найти, посмотрев на слово, чтобы увидеть, какие записи относятся к контейнеру, а затем просканировав постоянное количество записей (большинство современных процессоров поддерживают специальные операции по обработке битов, которые делают поиск в битовой карте «информации о переходе» очень быстрым).
Вот как добавить элемент x , который был хэширован, в контейнер i :
Идея заключается в том, что хеширование классиков «перемещает пустой слот в нужное ведро». Это отличает его от линейного зондирования , которое оставляет пустой слот там, где он был найден, возможно, далеко от исходного ведра, или от хеширования кукушки , которое для создания свободного ведра перемещает элемент из одного из нужных ведер в целевых массивах и только затем пытается найти перемещенный элемент на новом месте.
Чтобы удалить элемент из таблицы, нужно просто удалить его из записи таблицы. Если соседние контейнеры кэшированы, можно применить операцию реорганизации, в которой элементы перемещаются в теперь свободное место, чтобы улучшить выравнивание.
Одним из преимуществ хеширования по методу классиков является то, что оно обеспечивает хорошую производительность при очень высоких коэффициентах загрузки таблицы, даже превышающих 0,9. Частично эта эффективность обусловлена использованием линейного зонда только для поиска пустого слота во время вставки, а не для каждого поиска, как в исходном алгоритме линейного зондирования хеш-таблицы. Другое преимущество заключается в том, что можно использовать любую хеш-функцию, в частности простые, близкие к универсальным.
В статье также представлены несколько вариантов схемы хеширования «классики». [1]
Расширенный подход использует схему указателя для реализации слова информации о переходе (в базовом случае это битовая карта информации о переходе ). Это позволяет слову информации о переходе иметь произвольный (но фиксированный) размер.
Хотя базовый случай и расширенный подход разработаны как последовательные , для каждого из них также существует параллельный вариант.
Вариант без блокировки был представлен Робертом Келли, Бараком А. Перлмуттером и Филом Магуайром в 2020 году. [2]