Линейное зондирование

Конфликт между Джоном Смитом и Сандрой Ди (оба хешируются в ячейку 873) разрешается путем помещения Сандры Ди в следующее свободное место, ячейку 874.

Линейное зондирование - это схема в компьютерном программировании для разрешения коллизий в хэш-таблицах , структурах данных для поддержания коллекции пар ключ-значение и поиска значения, связанного с данным ключом. Он был изобретен в 1954 году Джином Амдалом , Элейн М. Макгроу и Артуром Самуэлем и впервые проанализирован в 1963 году Дональдом Кнутом .

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

Как пишут Thorup & Zhang (2012) : «Хеш-таблицы - это наиболее часто используемые нетривиальные структуры данных, а наиболее популярная реализация на стандартном оборудовании использует линейное зондирование, которое одновременно быстро и просто». ^[1] Линейное зондирование может обеспечить высокую производительность из-за хорошей локализации ссылки , но более чувствительно к качеству своей хэш-функции, чем некоторые другие схемы разрешения конфликтов. При реализации с использованием случайной хеш-функции, 5-независимой хеш-функции или хеширования табуляции требуется постоянное ожидаемое время на поиск, вставку или удаление . Хорошие результаты также могут быть достигнуты на практике с другими хэш-функциями, такими как MurmurHash . ^[2]

Операции [ править ]

Линейное зондирование - это компонент схем открытой адресации для использования хеш-таблицы для решения проблемы словаря . В проблеме словаря структура данных должна поддерживать коллекцию пар ключ-значение, подчиняющуюся операциям, которые вставляют или удаляют пары из коллекции или которые ищут значение, связанное с данным ключом. В открытых решениях этой проблемы структура данных представляет собой массив T (хеш-таблицу), каждая ячейка которого T [ i ] (когда она непуста) хранит одну пару ключ-значение. Хэш - функция используется для отображения каждого ключа в ячейку Tгде этот ключ должен храниться, как правило, путем шифрования ключей, чтобы ключи с одинаковыми значениями не располагались в таблице рядом друг с другом. Конфликт хеширования возникает, когда хеш-функция отображает ключ в ячейку, которая уже занята другим ключом. Линейное зондирование - это стратегия разрешения коллизий путем помещения нового ключа в ближайшую следующую пустую ячейку. ^{[3] [4]}

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

Для поиска заданного ключа x проверяются ячейки T , начиная с ячейки с индексом h ( x ) (где h - хеш-функция) и заканчивая соседними ячейками h ( x ) + 1 , h ( x ). + 2 , ..., пока не будет найдена пустая ячейка или ячейка, ключ которой равен x. Если ячейка, содержащая ключ, найдена, поиск возвращает значение из этой ячейки. В противном случае, если будет найдена пустая ячейка, ключ не может быть в таблице, потому что он был бы помещен в эту ячейку, а не в любую более позднюю ячейку, поиск в которой еще не проводился. В этом случае поиск возвращает в качестве результата, что ключ отсутствует в словаре. ^{[3] [4]}

Вставка [ править ]

Чтобы вставить пару "ключ-значение" ( x , v ) в таблицу (возможно, заменяя любую существующую пару тем же ключом), алгоритм вставки следует той же последовательности ячеек, которая использовалась бы при поиске, пока не будет найдена пустая ячейка. или ячейка, в которой хранится ключ x . Затем в эту ячейку помещается новая пара "ключ-значение". ^{[3] [4]}

Если вставка приведет к тому, что коэффициент загрузки таблицы (ее доля занятых ячеек) вырастет выше некоторого заданного порогового значения, вся таблица может быть заменена новой таблицей, увеличенной на постоянный коэффициент, с новой хеш-функцией, как в динамический массив . Установка этого порога близким к нулю и использование высокой скорости роста для размера таблицы приводит к более быстрым операциям с хеш-таблицей, но большему использованию памяти, чем пороговые значения, близкие к единице, и низким темпам роста. Обычным выбором было бы удвоить размер стола, когда коэффициент нагрузки превышает 1/2, в результате чего коэффициент нагрузки остается в пределах от 1/4 до 1/2. ^[5]

Удаление [ править ]

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

Вместо этого, когда ячейка i опустошается, необходимо искать вперед по следующим ячейкам таблицы, пока не найдет либо другую пустую ячейку, либо ключ, который можно переместить в ячейку i (то есть ключ, хеш-значение которого равно или раньше, чем i ). При обнаружении пустой ячейки очистка ячейки i безопасна, и процесс удаления завершается. Но когда поиск находит ключ, который можно переместить в ячейку i, он выполняет этот ход. Это ускоряет последующий поиск перемещенного ключа, но также очищает другую ячейку, позже в том же блоке занятых ячеек. Поиск подвижного ключа продолжается для новой пустой ячейки таким же образом, пока не завершится достижением ячейки, которая уже была пустой. В этом процессе перемещения ключей в более ранние ячейки каждый ключ проверяется только один раз. Следовательно, время завершения всего процесса пропорционально длине блока занятых ячеек, содержащего удаленный ключ, что соответствует времени выполнения других операций с хеш-таблицей. ^[3]

В качестве альтернативы можно использовать стратегию ленивого удаления , при которой пара ключ-значение удаляется путем замены значения специальным значением флага, указывающим на удаленный ключ. Однако значения этих флагов будут влиять на коэффициент загрузки хеш-таблицы. При использовании этой стратегии может потребоваться очистить значения флагов из массива и повторно хэшировать все оставшиеся пары ключ-значение, когда слишком большая часть массива будет занята удаленными ключами. ^{[3] [4]}

Свойства [ править ]

Линейное зондирование обеспечивает хорошую локальность ссылок , из-за чего для каждой операции требуется несколько обращений к некэшированной памяти. Из-за этого при коэффициенте нагрузки от низкого до среднего он может обеспечить очень высокую производительность. Однако, по сравнению с некоторыми другими стратегиями открытой адресации, его производительность ухудшается быстрее при высоких факторах нагрузки из-за первичной кластеризации , склонности одного столкновения вызывать большее количество соседних столкновений. ^[3] Кроме того, для достижения хорошей производительности с помощью этого метода требуется более качественная хеш-функция, чем для некоторых других схем разрешения конфликтов. ^[6]При использовании с низкокачественными хэш-функциями, которые не могут устранить неоднородности во входном распределении, линейное зондирование может быть медленнее, чем другие стратегии открытой адресации, такие как двойное хеширование , которое исследует последовательность ячеек, разделение которых определяется второй хеш-функцией, или квадратичное зондирование , где размер каждого шага варьируется в зависимости от его положения в последовательности зонда. ^[7]

Анализ [ править ]

Используя линейное зондирование, словарные операции могут выполняться за постоянное ожидаемое время . Другими словами, операции вставки, удаления и поиска могут быть реализованы в O (1) , если коэффициент загрузки хеш-таблицы является константой, строго меньшей единицы. ^[8]

Более подробно, время для любой конкретной операции (поиска, вставки или удаления) пропорционально длине непрерывного блока занятых ячеек, с которого начинается операция. Если все начальные ячейки равновероятны, в хеш-таблице с N ячейками, то максимальный блок из k занятых ячеек будет иметь вероятность k / N содержать начальное местоположение поиска и займет время O ( k ) всякий раз, когда это будет исходное место. Следовательно, ожидаемое время для операции можно рассчитать как произведение этих двух членов, O ( k ² / N ), суммированного по всем максимальным блокам смежных ячеек в таблице. Аналогичная сумма квадратов длин блоков дает ожидаемую временную границу для случайной хэш-функции (а не для случайного начального местоположения в конкретное состояние хеш-таблицы) путем суммирования всех блоков, которые могут существовать (а не тех, которые фактически существуют в данном состоянии таблицы), и умножая член для каждого потенциального блока на вероятность того, что блок действительно занят. То есть, определяя Block ( i , k ) как событие, когда существует максимальный непрерывный блок занятых ячеек длины k, начинающийся с индекса i , ожидаемое время на операцию равно

${\displaystyle E[T]=O(1)+\sum _{i=1}^{N}\sum _{k=1}^{n}O(k^{2}/N)\operatorname {Pr} [\operatorname {Block} (i,k)].}$

Эту формулу можно упростить, заменив Block ( i , k ) более простым необходимым условием Full ( k ) , когда по крайней мере k элементов имеют хеш-значения, лежащие в пределах блока ячеек длины k . После этой замены значение в сумме больше не зависит от i , а коэффициент 1 / N отменяет N членов внешнего суммирования. Эти упрощения приводят к оценке

${\displaystyle E[T]\leq O(1)+\sum _{k=1}^{n}O(k^{2})\operatorname {Pr} [\operatorname {Full} (k)].}$

Но в соответствии с мультипликативной формой границы Чернова , когда коэффициент нагрузки не равен единице, вероятность того, что блок длины k содержит не менее k хешированных значений, экспоненциально мала как функция от k , в результате чего эта сумма ограничивается величиной константа, не зависящая от  n . ^[3] Также можно выполнить тот же анализ, используя приближение Стирлинга вместо оценки Чернова, чтобы оценить вероятность того, что блок содержит ровно k хешированных значений. ^{[4] [9]}

С точки зрения коэффициента загрузки α , ожидаемое время успешного поиска составляет O (1 + 1 / (1 - α )) , а ожидаемое время неудачного поиска (или вставки нового ключа) составляет O (1 + 1 / (1 - α ) ² ) . ^[10] Для постоянных коэффициентов загрузки с высокой вероятностью самая длинная тестовая последовательность (среди тестовых последовательностей для всех ключей, хранящихся в таблице) имеет логарифмическую длину. ^[11]

Выбор хэш-функции [ править ]

Поскольку линейное зондирование особенно чувствительно к неравномерно распределенным хеш-значениям ^[7], важно сочетать его с высококачественной хеш-функцией, которая не создает таких отклонений.

Приведенный выше анализ предполагает, что хэш каждого ключа является случайным числом, независимым от хешей всех других ключей. Это предположение нереально для большинства приложений хеширования. Однако случайные или псевдослучайные хеш-значения могут использоваться при хешировании объектов по их идентичности, а не по их значению. Например, это выполняется с помощью линейного зондирования классом IdentityHashMap платформы коллекций Java . ^[12] Хэш-значение, которое этот класс связывает с каждым объектом, его identityHashCode, гарантированно остается фиксированным в течение всего времени существования объекта, но в остальном является произвольным. ^[13]Поскольку identityHashCode создается только один раз для каждого объекта и не обязательно должен быть связан с адресом или значением объекта, его построение может включать более медленные вычисления, такие как вызов генератора случайных или псевдослучайных чисел. Например, Java 8 использует генератор псевдослучайных чисел Xorshift для создания этих значений. ^[14]

Для большинства приложений хеширования необходимо вычислять хеш-функцию для каждого значения каждый раз, когда оно хешируется, а не один раз при создании его объекта. В таких приложениях случайные или псевдослучайные числа не могут использоваться в качестве хеш-значений, потому что тогда разные объекты с одинаковым значением будут иметь разные хеш-коды. А криптографические хэш-функции (которые разработаны так, чтобы их нельзя было отличить в вычислительном отношении от действительно случайных), обычно слишком медленны для использования в хеш-таблицах. ^[15] Вместо этого были разработаны другие методы построения хеш-функций. Эти методы быстро вычисляют хеш-функцию, и может быть доказано, что они хорошо работают с линейным зондированием. В частности, линейное зондирование было проанализировано в рамках k-независимое хеширование , класс хэш-функций, которые инициализируются из небольшого случайного начального числа и которые с одинаковой вероятностью отображают любой k -набор различных ключей в любой k -набор индексов. Параметр k можно рассматривать как меру качества хеш-функции: чем больше k , тем больше времени потребуется для вычисления хеш-функции, но она будет вести себя более похоже на полностью случайные функции. Для линейного зондирования 5-независимости достаточно, чтобы гарантировать постоянное ожидаемое время на операцию ^{[16], в} то время как некоторые 4-независимые хеш-функции работают плохо, занимая до логарифмического времени на операцию. ^[6]

Еще один метод построения хеш-функций с высоким качеством и практической скоростью - это хеширование таблиц . В этом методе хеш-значение для ключа вычисляется с использованием каждого байта ключа в качестве индекса в таблице случайных чисел (с другой таблицей для каждой позиции байта). Затем числа из этих ячеек таблицы объединяются побитовой операцией исключающее или . Хэш-функции, построенные таким образом, независимы только от трех. Тем не менее, линейное зондирование с использованием этих хэш-функций требует постоянного ожидаемого времени на одну операцию. ^{[4] [17]} И хеширование табуляции, и стандартные методы генерации 5-независимых хеш-функций ограничены ключами с фиксированным числом битов. Для обработки струнили других типов ключей переменной длины, можно составить более простой универсальный метод хеширования , который сопоставляет ключи с промежуточными значениями, и хэш-функцию более высокого качества (5-независимую или табулированную), которая сопоставляет промежуточные значения с индексами хеш-таблицы. ^{[1] [18]}

В экспериментальном сравнении Richter et al. обнаружили, что семейство хэш-функций Multiply-Shift (определяемых как ) было «самой быстрой хеш-функцией при интеграции со всеми схемами хеширования, т. е. обеспечивающей наивысшую пропускную способность, а также хорошее качество», тогда как хеширование с использованием таблиц производило «самую низкую пропускную способность». ^[2] Они отмечают, что каждый просмотр таблицы требует нескольких циклов, что дороже, чем простые арифметические операции. Они также обнаружили, что MurmurHash превосходит хеширование табуляции: «Изучая результаты, предоставленные Mult и Murmur, мы думаем, что компромисс табуляции (...) на практике менее привлекателен».${\displaystyle h_{z}(x)=(x\cdot z{\bmod {2}}^{w})\div 2^{w-d}}$

История [ править ]

Идея ассоциативного массива , что позволяет получать данные доступны его стоимости , а не по его адресу восходит к середине 1940-х годов в работе Конрада Цузе и Ванневар Буша , ^[19] , но хэш - таблицы были не описаны до 1953 года, в меморандум IBM Ханса Петера Луна . Лун использовал другой метод разрешения столкновений, цепочку, а не линейное зондирование. ^[20]

Кнут  ( 1963 ) подводит итог ранней истории линейного зондирования. Это был первый метод открытой адресации, который изначально был синонимом открытой адресации. По словам Кнута, он был впервые использован Джином Амдалом , Элейн М. Макгро (урожденная Бёме) и Артуром Самуэлем в 1954 году в программе ассемблера для компьютера IBM 701 . ^[8] Первое опубликованное описание линейного зондирования принадлежит Петерсону (1957) , ^[8], который также доверяет Самуэлю, Амдалу и Бёме, но добавляет, что «система настолько естественна, что весьма вероятно, что она была задумана независимо другими. либо до, либо с того времени ». ^[21]Еще одна ранняя публикация этого метода была опубликована советским исследователем Андреем Ершовым в 1958 г. ^[22]

Кнут дал первый теоретический анализ линейного зондирования, показывающий, что на операцию со случайными хэш-функциями требуется постоянное ожидаемое время. ^[8] Седжвик называет работу Кнута «вехой в анализе алгоритмов». ^[10] Значительные более поздние разработки включают более подробный анализ распределения вероятностей времени работы ^{[23] [24]} и доказательство того, что линейное зондирование выполняется за постоянное время на операцию с практически используемыми хеш-функциями, а не с идеализированными случайными функциями. предполагалось ранее проведенным анализом. ^{[16] [17]}

Ссылки [ править ]