Линейное зондирование
Линейное зондирование — это схема в компьютерном программировании для разрешения коллизий в хеш-таблицах , структурах данных для поддержания коллекции пар ключ-значение и поиска значения, связанного с данным ключом. Он был изобретен в 1954 году Джином Амдалом , Элейн М. МакГроу и Артуром Сэмюэлем и впервые проанализирован в 1963 году Дональдом Кнутом .
Наряду с квадратичным зондированием и двойным хешированием , линейное зондирование является формой открытой адресации . В этих схемах каждая ячейка хеш-таблицы хранит одну пару ключ-значение. Когда хеш-функция вызывает коллизию, сопоставляя новый ключ с ячейкой хеш-таблицы, которая уже занята другим ключом, линейное зондирование ищет в таблице ближайшее свободное место и вставляет туда новый ключ. Поиск выполняется таким же образом, путем последовательного поиска в таблице, начиная с позиции, заданной хэш-функцией, до тех пор, пока не будет найдена ячейка с совпадающим ключом или пустая ячейка.
Как пишут Торуп и Чжан (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 , он выполняет это перемещение. Это ускоряет последующие поиски перемещенного ключа, но также очищает другую ячейку, расположенную позже в том же блоке занятых ячеек. Поиск подвижного ключа продолжается для новой опустевшей ячейки таким же образом, пока не завершится достижением уже пустой ячейки. В этом процессе перемещения ключей в более ранние ячейки каждый ключ проверяется только один раз. Следовательно, время завершения всего процесса пропорционально длине блока занятых ячеек, содержащих удаленный ключ, что соответствует времени выполнения других операций с хеш-таблицей. [3]
В качестве альтернативы можно использовать стратегию отложенного удаления , при которой пара ключ-значение удаляется путем замены значения специальным значением флага, указывающим удаленный ключ. Однако эти значения флагов будут способствовать коэффициенту загрузки хеш-таблицы. При использовании этой стратегии может возникнуть необходимость очистить значения флагов из массива и перехешировать все оставшиеся пары ключ-значение, если слишком большая часть массива будет занята удаленными ключами. [3] [4]
Свойства [ править ]
Линейное зондирование обеспечивает хорошую локальность ссылки , что приводит к необходимости небольшого количества обращений к некэшированной памяти на одну операцию. Благодаря этому при низких и средних факторах нагрузки он может обеспечить очень высокую производительность. Однако, по сравнению с некоторыми другими стратегиями открытой адресации, его производительность снижается быстрее при высоких коэффициентах нагрузки из-за первичной кластеризации — тенденции, когда одно столкновение вызывает больше соседних конфликтов. [3] Кроме того, для достижения хорошей производительности с помощью этого метода требуется хеш-функция более высокого качества, чем для некоторых других схем разрешения коллизий. [6] При использовании с хэш-функциями низкого качества, которые не могут устранить неоднородности во входном распределении, линейное зондирование может быть медленнее, чем другие стратегии открытой адресации, такие как двойное хеширование , которое исследует последовательность ячеек, разделение которых определяется второй хеш-функцией. или квадратичное зондирование , где размер каждого шага варьируется в зависимости от его положения в последовательности зондирования. [7]
Анализ [ править ]
Используя линейное зондирование, словарные операции могут быть реализованы за постоянное ожидаемое время . Другими словами, операции вставки, удаления и поиска могут быть реализованы за O(1) до тех пор, пока коэффициент загрузки хеш-таблицы является константой, строго меньшей единицы. [8]
Более подробно, время для любой конкретной операции (поиска, вставки или удаления) пропорционально длине непрерывного блока занятых ячеек, с которого начинается операция. Если все начальные ячейки одинаково вероятны в хеш-таблице с N ячейками, то максимальный блок из k занятых ячеек будет иметь вероятность k / N содержать начальное местоположение поиска и будет занимать время O ( k ), когда бы это ни было . стартовая локация. Следовательно, ожидаемое время операции можно рассчитать как произведение этих двух слагаемых O ( k 2 / 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)].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8d627679f56340b4179de1a31e927cdc790d4cb)
Эту формулу можно упростить, заменив 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)]. }](https://wikimedia.org/api/rest_v1/media/math/render/svg/3e9c4905218ddf4e9f1b1d30edfb0b846fd14262)
Но согласно мультипликативной форме границы Чернова , когда коэффициент загрузки отделен от единицы, вероятность того, что блок длины k содержит по крайней мере k хешированных значений, экспоненциально мала как функция k ,в результате чего эта сумма будет ограничена константой, не зависящей от n . [3] Также можно выполнить тот же анализ, используя приближение Стирлинга вместо границы Чернова, чтобы оценить вероятность того, что блок содержит ровно k хешированных значений. [4] [9]
С точки зрения коэффициента загрузки α ожидаемое время выполнения успешного поиска по случайному ключу равно O (1 + 1/(1 − α )) , а ожидаемое время выполнения неудачного поиска (или вставки нового ключ) равен O (1 + 1/(1 − α ) 2 ) . [10] При постоянных коэффициентах нагрузки с большой вероятностью самая длинная пробная последовательность (среди пробных последовательностей для всех ключей, хранящихся в таблице) имеет логарифмическую длину. [11]
Первичная кластеризация [ править ]
Хэш-таблицы линейного зондирования страдают от проблемы, известной как первичная кластеризация , при которой элементы группируются в длинные последовательные прогоны. [12] [10] С точки зрения коэффициента загрузки α ожидаемая длина пробега, содержащего данный элемент, равна . [10] Вот почему вставки занимают время , в отличие от времени выполнения достигается с помощью других хэш-таблиц с открытым адресом, таких как равномерное зондирование и двойное хеширование . [10] Первичная кластеризация также влияет на неудачные поиски, поскольку, как и вставки, они должны дойти до конца цикла. [10] Некоторые варианты линейного зондирования позволяют добиться лучших оценок для неудачных поисков и вставок за счет использования методов, уменьшающих первичную кластеризацию. [13]
Выбор хеш-функции [ править ]
Поскольку линейное зондирование особенно чувствительно к неравномерному распределению хеш-значений, [7] важно объединить его с качественной хеш-функцией, которая не выдает подобных нарушений.
В приведенном выше анализе предполагается, что хеш каждого ключа представляет собой случайное число, независимое от хэшей всех остальных ключей. Это предположение нереалистично для большинства приложений хеширования.Однако случайные или псевдослучайные значения хеш-функции могут использоваться при хешировании объектов по их идентификаторам, а не по их значению. Например, это делается с помощью линейного зондирования классом IdentityHashMap платформы коллекций Java . [14] Хэш-значение, которое этот класс связывает с каждым объектом, его идентификаторidentHashCode, гарантированно остается фиксированным на протяжении всего времени существования объекта, но в остальном является произвольным. [15] Поскольку идентификаторidentHashCode создается только один раз для каждого объекта и не обязательно должен быть связан с адресом или значением объекта, его создание может включать более медленные вычисления, такие как вызов генератора случайных или псевдослучайных чисел . Например, Java 8 использует генератор псевдослучайных чисел Xorshift для создания этих значений. [16]
Для большинства приложений хеширования необходимо вычислять хеш-функцию для каждого значения каждый раз, когда оно хэшируется, а не один раз при создании его объекта. В таких приложениях случайные или псевдослучайные числа не могут использоваться в качестве значений хеш-функции, поскольку тогда разные объекты с одним и тем же значением будут иметь разные хеш-функции. А криптографические хеш-функции (которые спроектированы так, чтобы их вычислительно было невозможно отличить от действительно случайных функций) обычно слишком медленны, чтобы их можно было использовать в хеш-таблицах. [17] Вместо этого были разработаны другие методы построения хэш-функций. Эти методы быстро вычисляют хеш-функцию, и можно доказать, что они хорошо работают при линейном зондировании. В частности, линейное зондирование анализировалось в рамках k -независимого хеширования — класса хэш-функций, которые инициализируются из небольшого случайного начального числа и с равной вероятностью отображают любой k -кортеж различных ключей в любой k -кортеж из индексы. Параметр k можно рассматривать как меру качества хеш-функции: чем больше k , тем больше времени потребуется для вычисления хеш-функции, но она будет вести себя более похоже на полностью случайные функции.Для линейного зондирования пятикратной независимости достаточно, чтобы гарантировать постоянное ожидаемое время на операцию. [18] в то время как некоторые 4-независимые хэш-функции работают плохо, занимая до логарифмического времени на каждую операцию. [6]
Еще один метод построения хэш-функций, обладающий одновременно высоким качеством и практичной скоростью, — это табулационное хеширование . В этом методе хеш-значение ключа вычисляется путем использования каждого байта ключа в качестве индекса в таблице случайных чисел (с отдельной таблицей для каждой позиции байта). Числа из этих ячеек таблицы затем объединяются с помощью побитовой исключающей операции или . Хэш-функции, построенные таким образом, независимы только от 3. Тем не менее, линейное зондирование с использованием этих хеш-функций занимает постоянное ожидаемое время на операцию. [4] [19] Как табулационное хеширование, так и стандартные методы генерации 5-независимых хэш-функций ограничены ключами, имеющими фиксированное количество бит. Для обработки строк или других типов ключей переменной длины можно создать более простой универсальный метод хеширования , который сопоставляет ключи с промежуточными значениями, и хеш-функцию более высокого качества (5-независимую или табулируемую), которая отображает промежуточные значения в хеш-таблицу. индексы. [1] [20]
В экспериментальном сравнении Richter et al. обнаружил, что семейство хэш-функций Multiply-Shift (определенное как ) была «самой быстрой хэш-функцией при интеграции со всеми схемами хеширования, т. е. обеспечивающей самую высокую пропускную способность, а также хорошего качества», тогда как табулационное хеширование давало «самую низкую пропускную способность». [2] Они отмечают, что каждый поиск в таблице требует нескольких циклов и является более затратным, чем простые арифметические операции. Они также обнаружили, что MurmurHash превосходит табулированное хеширование: «Изучая результаты, предоставленные Mult и Murmur, мы считаем, что компромисс в пользу табуляции (...) менее привлекателен на практике».
История [ править ]
Идея ассоциативного массива , позволяющего осуществлять доступ к данным по их значению, а не по адресу, восходит к середине 1940-х годов в работах Конрада Цузе и Ванневара Буша . [21] но хэш-таблицы не были описаны до 1953 года в меморандуме IBM Ханса Питера Луна . Лун использовал другой метод разрешения коллизий — цепочку, а не линейное зондирование. [22]
Кнут ( 1963 ) суммирует раннюю историю линейного зондирования. Это был первый метод открытой адресации, который изначально был синонимом открытой адресации. По словам Кнута, его впервые использовали Джин Амдал , Элейн М. МакГроу (урожденная Беме) и Артур Сэмюэл в 1954 году в ассемблерной программе для компьютера IBM 701 . [8] Первое опубликованное описание линейного зондирования принадлежит Петерсону (1957) . [8] который также отдает должное Самуэлю, Амдалу и Беме, но добавляет, что «система настолько естественна, что, весьма вероятно, могла быть задумана другими независимо до или после этого времени». [23] Еще одна ранняя публикация этого метода была советским исследователем Андреем Ершовым в 1958 году. [24]
Первый теоретический анализ линейного зондирования, показывающий, что на операцию со случайными хеш-функциями требуется постоянное ожидаемое время, был проведен Кнутом. [8] Седжвик называет работу Кнута «вехой в анализе алгоритмов». [10] Значительные более поздние разработки включают более подробный анализ вероятностного распределения времени работы, [25] [26] и доказательство того, что линейное зондирование выполняется за постоянное время на каждую операцию с практически применимыми хеш-функциями, а не с идеализированными случайными функциями, предполагаемыми предыдущим анализом. [18] [19]
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б Торуп, Миккель ; Чжан, Инь (2012), «5-независимое хеширование на основе таблиц с приложениями к линейному зондированию и оценке второго момента», SIAM Journal on Computing , 41 (2): 293–331, doi : 10.1137/100800774 , MR 2914329
- ^ Jump up to: Перейти обратно: а б Рихтер, Стефан; Альварес, Виктор; Диттрих, Йенс (2015), «Семимерный анализ методов хеширования и его влияние на обработку запросов» (PDF) , Proceedings of the VLDB Endowment , 9 (3): 293–331, doi : 10.14778/2850583.2850585
- ^ Jump up to: Перейти обратно: а б с д и ж г Гудрич, Майкл Т .; Тамассиа, Роберто (2015), «Раздел 6.3.3: Линейное зондирование», Разработка и применение алгоритмов , Wiley, стр. 200–203.
- ^ Jump up to: Перейти обратно: а б с д и ж Морин, Пэт (22 февраля 2014 г.), «Раздел 5.2: LinearHashTable: линейное зондирование», Структуры открытых данных (в псевдокоде) (0.1G β -ред.), стр. 108–116 , получено 15 января 2016 г.
- ^ Седжвик, Роберт ; Уэйн, Кевин (2011), Алгоритмы (4-е изд.), Addison-Wesley Professional, стр. 471, ISBN 9780321573513 . Седжвик и Уэйн также уменьшают вдвое размер таблицы, когда удаление приводит к тому, что коэффициент загрузки становится слишком низким, что заставляет их использовать более широкий диапазон [1/8,1/2] возможных значений коэффициента загрузки.
- ^ Jump up to: Перейти обратно: а б Патрашку, Михай ; Торуп, Миккель (2010), «О k -независимости, необходимой для линейного зондирования и минимальной независимости» (PDF) , Автоматы, языки и программирование , 37-й международный коллоквиум, ICALP 2010, Бордо, Франция, 6–10 июля 2010 г., Материалы , Часть I , Конспект лекций по информатике , вып. 6198, Springer, стр. 715–726, arXiv : 1302.5127 , doi : 10.1007/978-3-642-14165-2_60.
- ^ Jump up to: Перейти обратно: а б Хейлеман, Грегори Л.; Луо, Вэньбинь (2005), «Как кэширование влияет на хеширование» (PDF) , Седьмой семинар по разработке алгоритмов и экспериментам (ALENEX 2005) , стр. 141–154.
- ^ Jump up to: Перейти обратно: а б с д Кнут, Дональд (1963), Заметки об «открытой» адресации , заархивировано из оригинала 3 марта 2016 г.
- ^ Эппштейн, Дэвид (13 октября 2011 г.), «Линейное измерение стало проще» , 0xDE
- ^ Jump up to: Перейти обратно: а б с д и ж Седжвик, Роберт (2003), «Раздел 14.3: Линейное зондирование», Алгоритмы на Java, Части 1–4: Основы, структуры данных, сортировка, поиск (3-е изд.), Аддисон Уэсли, стр. 615–620, ISBN 9780321623973
- ^ Питтель, Б. (1987), «Линейное зондирование: вероятное наибольшее время поиска логарифмически растет с количеством записей», Journal of Algorithms , 8 (2): 236–249, doi : 10.1016/0196-6774(87)90040 -Х , МР 0890874
- ^ Кормен, Томас Х.; Лейзерсон, Чарльз Эрик; Ривест, Рональд Линн; Штейн, Клиффорд (2009). Введение в алгоритмы (3-е изд.). Кембридж, Массачусетс, Лондон, Англия: MIT Press. ISBN 978-0-262-53305-8 .
- ^ Бендер, Майкл А.; Кушмаул, Брэдли С.; Кушмаул, Уильям (2022). «Возвращение к линейному зондированию: надгробия знаменуют упадок первичной кластеризации» . 62-й ежегодный симпозиум IEEE по основам информатики (FOCS) , 2021 г. IEEE. стр. 1171–1182. дои : 10.1109/focs52979.2021.00115 . ISBN 978-1-6654-2055-6 . S2CID 260502788 .
- ^ «IdentityHashMap» , Документация Java SE 7 , Oracle , получено 15 января 2016 г.
- ^ Фризен, Джефф (2012), Начало Java 7 , Голос эксперта по Java, Apress, стр. 376, ISBN 9781430239109
- ^ Кабуц, Хайнц М. (9 сентября 2014 г.), «Кризис идентичности» , Информационный бюллетень специалистов по Java , 222
- ^ Вайс, Марк Аллен (2014), «Глава 3: Структуры данных» , в Гонсалесе, Теофило; Диас-Эррера, Хорхе; Такер, Аллен (ред.), Справочник по вычислительной технике , том. 1 (3-е изд.), CRC Press, с. 3–11, ISBN 9781439898536 .
- ^ Jump up to: Перейти обратно: а б Паг, Анна; Паг, Расмус ; Ружич, Милан (2009), «Линейное зондирование с постоянной независимостью», SIAM Journal on Computing , 39 (3): 1107–1120, arXiv : cs/0612055 , doi : 10.1137/070702278 , MR 2538852
- ^ Jump up to: Перейти обратно: а б Патрашку, Михай ; Торуп, Миккель (2011), «Сила простого хеширования таблиц», Труды 43-го ежегодного симпозиума ACM по теории вычислений (STOC '11) , стр. 1–10, arXiv : 1011.5200 , doi : 10.1145/1993636.1993638 , S2CID 195776653
- ^ Торуп, Миккель (2009), «Хеширование строк для линейного зондирования», Труды двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам , Филадельфия, Пенсильвания: SIAM, стр. 655–664, CiteSeerX 10.1.1.215.4253 , doi : 10.1137 /1.9781611973068.72 , МР 2809270
- ^ Пархами, Бехруз (2006), Введение в параллельную обработку: алгоритмы и архитектуры , Серия по компьютерным наукам, Springer, 4.1 Разработка ранних моделей, с. 67, ISBN 9780306469640
- ^ Морин, Пэт (2004), «Хеш-таблицы» , Мехта, Динеш П.; Сахни, Сартадж (ред.), Справочник по структурам данных и приложениям , Chapman & Hall / CRC, стр. 9–15, ISBN 9781420035179 .
- ^ Петерсон, WW (апрель 1957 г.), «Адресация для хранения с произвольным доступом», IBM Journal of Research and Development , 1 (2), Ривертон, Нью-Джерси, США: IBM Corp.: 130–146, doi : 10.1147/rd.12.0130
- ^ Ершов А. П. (1958), «О программировании арифметических операций», Сообщения АКМ , 1 (8): 3–6, doi : 10.1145/368892.368907 , S2CID 15986378 . Перевод Морриса Д. Фридмана из Докладов АН СССР, 118 (3): 427–430, 1958. Линейное зондирование описывается как алгоритм А2.
- ^ Флажоле, П. ; Поблете, П.; Виола, А. (1998), «Об анализе линейного зондирующего хеширования» (PDF) , Algorithmica , 22 (4): 490–515, doi : 10.1007/PL00009236 , MR 1701625 , S2CID 5436036
- ^ Кнут, DE (1998), «Линейное зондирование и графики», Algorithmica , 22 (4): 561–568, arXiv : cs/9801103 , doi : 10.1007/PL00009240 , MR 1701629 , S2CID 12254909