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

Материал из Поле цифровой дидактики
Файл:HASHTB12.svg
Коллизия между записями «John Smith» и «Sandra Dee» (обе записи имеют хеш-значение 873) разрешается помещением записи «Sandra Dee» на следующее свободное место, ячейку 874.

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

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

Как писали Торуп и Чжан, «Хеш-таблицы интенсивно используют нетривиальные структуры данных и большинство имплементаций в аппаратуре использует линейное зондирование, быстрое и простое в реализации»Шаблон:Sfn. Линейное зондирование может дать высокую производительность вследствие хорошей Шаблон:Не переведено 5 метода, но оно более чувствительно к качеству хеш-функции, чем другие схемы разрешения коллизий. Среднее ожидаемое время поиска у метода является константой, то же самое верно для вставки и удаления, если в имплементации используется случайный выбор хеш-функции, Шаблон:Не переведено 5, или Шаблон:Не переведено 5. Однако, на практике, хорошие результаты получаются и с другими функциями хеширования, такими как MurmurHash Шаблон:Sfn.

Операции

Линейное зондирование является компонентом схем Шаблон:Не переведено 5 для использования в хеш-таблицах для решения словарных задач. В словарной задаче структура данных должна работать с набором пар ключ-значение и должна обеспечивать возможность вставки и удаления пар, а также поиск значения, ассоциированного с ключом. В открытой адресации структурой данных служит массив Шаблон:Mvar (хеш-таблица), ячейки которого Шаблон:Math (если не пусты) содержат единственную пару ключ-значение. Хеш-функция используется для отображения каждого ключа в ячейку таблицы Шаблон:Mvar, куда этот ключ должен быть занесён, как правило, скремблируя ключи, так что ключи с близкими значениями не оказываются близко в таблице. Коллизия хеш-функции возникает, когда хеш-функция отображает ключ в ячейку, уже занятую другим ключом. Линейное зондирование является стратегией для разрешения коллизий путём размещения нового ключа в ближайшую следующую свободную ячейкиШаблон:SfnШаблон:Sfn.

Поиск

Для поиска заданного ключа Шаблон:Mvar проверяются ячейки таблицы Шаблон:Mvar, начиная с ячейки с индексом Шаблон:Math (где Шаблон:Mvar — хеш-функция), затем ячейки Шаблон:Math, Шаблон:Math, …, пока не будет найдена свободная ячейка или ячейка, в которой содержится ключ Шаблон:Mvar. Если ячейка, содержащая ключ, найдена, процедура поиска возвращает значение из этой ячейки. В противном случае, если встретилась пустая ячейка, ключ не может находиться в таблице и процедура возвращает в качестве результата, что ключ не найденШаблон:SfnШаблон:Sfn

Вставка

Для вставки пары ключ-значение Шаблон:Math в таблицу (возможно, с заменой любой существующей пары с тем же ключом) алгоритм вставки проходит ту же последовательность ячеек, что и при поиске, пока не найдёт либо пустую ячейку, либо ячейку, содержащую ключ Шаблон:Mvar. Новая пара ключ-значение размещается в этой ячейкеШаблон:SfnШаблон:Sfn.

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

Удаление

Файл:Linear Probing Deletion.png
Когда удаляется пара ключ-значение, может оказаться необходимым перенести другую пару в эту ячейку, чтобы избежать получение пустой ячейки при поиске удалённого ключа

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

Таким образом, при очистке ячейки Шаблон:Mvar необходимо просмотреть последующие ячейки, пока не найдём пустую ячейку, либо ключ, который можно перенести в ячейку Шаблон:Mvar (то есть ключ, хеш-значение которого равно или меньше Шаблон:Mvar). Если найдена пустая ячейка, то можно очистить ячейку Шаблон:Mvar и остановить процесс удаления. Если же найден ключ, который можно перенести в ячейку Шаблон:Mvar, переносим его. Это приведёт к увеличению скорости поиска перенесённого ключа, а также очищает другую ячейку в блоке занятых ячеек. Необходимо продолжить поиск ключа, который может быть перенесён на это освободившееся место. Поиск ключа для переноса осуществляется до пустой ячейки, пока не достигнем ячейки, которая изначально была пуста. Таким образом, время выполнения всего процесса удаления пропорционально длине блока, содержащего удалённый ключШаблон:Sfn.

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

Свойства

Линейное зондирование даёт хорошую Шаблон:Не переведено 5, что означает, что нужно лишь несколько некешированных операций доступа к память на одну операцию. Ввиду этого, при поддержке низкого коэффициента загрузки алгоритм может дать высокую степень производительности. Однако, по сравнению с некоторыми другими стратегиями открытой адресации, скорость работы деградирует быстрее при высокой степени загрузки ввиду Шаблон:Не переведено 5, тенденции одной коллизии вызывать много близких коллизий Шаблон:Sfn. Кроме того, для получения хорошей скорости работы этого метода требуется хеш-функция более высокого качества, чем для других схем разрешения коллизийШаблон:Sfn. Если алгоритм реализуется с хеш-функцией низкого качества, которая не исключает неоднородности во входном распределении, линейное зондирование может оказаться медленнее других стратегий открытой адресации, таких как Шаблон:Не переведено 5, которое пробует последовательность ячеек, разъединение которых определяется второй хеш-функцией, или Шаблон:Не переведено 5, когда размер каждого шага меняется в зависимости от позиции в последовательности пробШаблон:Sfn.

Анализ

При использовании линейного зондирования операции со словарём могут быть имплементированы с постоянным ожидаемым временем доступа. Другими словами, операции вставки, удаления и поиска могут быть имплементированы за O(1), при условии, что коэффициент загрузки хеш-таблицы является константой, строго меньшей единицыШаблон:Sfn.

Подробнее, время для каждой отдельной операции (поиск, вставка или удаление) пропорционально длине непрерывного блока занятых ячеек, с которого операция начинается. Если все начальные ячейки равновозможны в хеш-таблице с Шаблон:Mvar ячейками, то максимальный блок Шаблон:Mvar занятых ячеек имеет вероятность Шаблон:Math содержать начальное положение поиска и займёт время Шаблон:Math, где бы ни находилась стартовая ячейка. Таким образом, ожидаемое время выполнения операции можно вычислить как произведение этих двух членов, Шаблон:Math, суммированных по всем максимальным блокам непрерывных ячеек в таблице. Похожая сумма квадратов длин блоков дают границу мат. ожидания времени для случайной хеш-функции (а не случайное стартовое положение в хеш-таблице) путём суммирования по всем блокам, которые могут существовать (а не по тем, которые фактически существуют в текущем состоянии таблицы) и умножения членов для каждого потенциального блока на вероятность, что блок занят. То есть, если определить Шаблон:Math как событие, что имеется максимальный непрерывный блок занятых ячеек длины Шаблон:Mvar, начинающийся с индекса Шаблон:Mvar, мат. ожидание времени на операцию равно

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

Формулу можно упростить путём замены Шаблон:Math by a simpler necessary condition Шаблон:Math, the event that at least Шаблон:Mvar elements have hash values that lie within a block of cells of length Шаблон:Mvar. After this replacement, the value within the sum no longer depends on Шаблон:Mvar, and the Шаблон:Math factor cancels the Шаблон:Mvar terms of the outer summation. Эти упрощения приводят к границе

[math]\displaystyle{ E[T] \le O(1) + \sum_{k=1}^n O(k^2) \operatorname{Pr}[\operatorname{Full}(k)]. }[/math]

Но, согласно мультипликативной форме границы Чернова, если коэффициент загрузки строго меньше единицы, вероятность, что длина блока Шаблон:Mvar содержит по меньшей мере Шаблон:Mvar хешированных значений, является экспоненциально малой как функция от Шаблон:Mvar, что означает, что сумма ограничена константой, не зависящей от Шаблон:MvarШаблон:Sfn. Можно также провести тот же анализ с помощью формулы Стирлинга вместо границы Чернова, чтобы оценить вероятность того, что блок содержит в точности Шаблон:Mvar хешированных значенийШаблон:SfnШаблон:Sfn.

В терминах коэффициента загрузки Шаблон:Mvar ожидаемое время успешного поиска равно Шаблон:Math, а ожидаемое время неуспешного поиска (или вставки нового ключа) равно Шаблон:Math Шаблон:Sfn. Для постоянного коэффициента загрузки, с большой вероятностью, самая длинная последовательность зондирования (среди последовательностей зондирования для всех ключей из таблицы) имеет логарифмическую длинуШаблон:Sfn.

Выбор Хеш-функции

Поскольку линейное зондирование очень чувствительно для неравномерно распределённых значений хеш-функцийШаблон:Sfn, важно комбинировать метод с хеш-функцией высокого качества, которая не даёт такую неравномерность.

Анализ, приведённый выше, предполагает, что хеш каждого ключа является случайным числом, не зависящим от хешей других ключей. Это предположение нереалистично для большинства приложений с хешированием. Однако случайные или псевдослучайные хеш-значения могут быть использованы, когда объекты хешируются по их идентификатору, а не по значению. Например, так сделано с использованием линейного зондирования с помощью класса IdentityHashMap в наборе классов и интерфейсов Java collections frameworkШаблон:Sfn. Значение хеша, который этот класс ассоциирует с каждым объектом, его identityHashCode, гарантированно остаётся неизменным для объекта на протяжении его жизни, но хеш-значение для такого же объекта в других обстоятельствах будет другимШаблон:Sfn. Поскольку identityHashCode строится только раз для каждого объекта и не требуется его связь со значением или адресом объекта, его построение может использовать более медленные вычислительные средства, такие как вызов случайных или псевдослучайных генераторов чисел. Например, Java 8 для построения таких значений использует псевдослучайный числовой генератор XorshiftШаблон:Sfn.

Для большинства приложений хеширования необходимо вычислять хеш-функцию для каждого значения каждый раз, когда требуется хеш, а не один раз, когда объект создаётся. В таких приложениях случайные или псевдослучайные числа не могут быть использованы в качестве хеш-значений, поскольку тогда различные объекты с тем же значением могли бы иметь различные значения хеша. А криптографические хеш-функции (которые создаются так, что они неотличимы от истинно случайных функций) обычно слишком медленны для использования в хеш-таблицахШаблон:Sfn. Вместо этого используются другие методы для построения хеш-функций. Эти методы вычисляют хеш-функцию быстро, и можно доказать, что они хорошо работают с линейным зондированием. В частности, линейное зондирование было проанализировано в рамках Шаблон:Не переведено 5, классе хеш-функций, которые инициализируются небольшим случайным числом с равной возможностью отображают любой Шаблон:Mvar-кортеж различных ключей в любой Шаблон:Mvar-кортеж индексов. Параметр Шаблон:Mvar может рассматриваться как мера качества хеш-функции — чем больше Шаблон:Mvar, тем больше времени нужно для вычисления хеш-функции, но она будет вести себя ближе к полностью случайным функциям. Для линейного зондирования 5-независимость достаточна, чтобы гарантировать постоянное ожидаемое время на операциюШаблон:Sfn, в то время как некоторые 4-независимые хеш-функции работают плохо, требуя логарифмического времени на операциюШаблон:Sfn.

Другой метод построения хеш-функций с высоким качеством и приемлемой скоростью — Шаблон:Не переведено 5. В этом методе значение хеша для ключа вычисляется путём выбора для каждого байта ключа индекса в таблице случайных чисел (с различными таблицами для каждой позиции байта). Числа из ячеек этих таблиц затем комбинируются побитно с помощью операции «исключающее ИЛИ». Хеш-функции, построенные таким образом, только 3-независимы. Тем не менее, линейные зондирования, использующие эти хеш-функции, требуют постоянного ожидаемого времени на операциюШаблон:SfnШаблон:Sfn. Как табличное хеширование, так и стандартные методы генерации 5-независимых хеш-функций лимитированы ключами, которые имеют фиксированное число бит. Для работы со строками или другими типами ключей переменной длины, можно Шаблон:Не переведено 5 более простую технику универсального хеширования, которая отображает ключи в промежуточные значения, с высокого качества (5-независимость или табуляция) хеш-функцией, которая отображает промежуточные значения в индексы хеш-таблицыШаблон:SfnШаблон:Sfn.

В экспериментальных сравнениях Рихтер и др. нашли, что семейство хеш-функций с кратным сдвигом (определённых как [math]\displaystyle{ h_z(x)=(x \cdot z \bmod 2^w) \div 2^{w-d} }[/math]) было «наиболее быстрой хеш-функцией при использовании во всех схемах хеширования, то есть дающая самую высокую пропускную способность, а также хорошее качество», в то время как табличное хеширование давало «самую низкую пропускную способность»Шаблон:Sfn. Они указали, что просмотр каждой таблицы требует несколько циклов, что более накладно, чем простые арифметические операции. Они также обнаружили, что MurmurHash лучше, чем табличное хеширование: «После изучения результатов, представленных Мультом и Мурмуром, мы думаем, что замена на табуляцию (…) на практике менее привлекательна».

История

Идея ассоциативного массива, которая позволяет получить доступ к данным по их значению, а не через их адрес, восходит к середине 1940-х годов к работам Конрада Цузе и Вэнивара БушаШаблон:Sfn, но хеш-таблицы не были описаны, пока их не описал Шаблон:Не переведено 5 в меморандуме IBM в 1953. Лун использовал другой метод разрешения коллизий, связь в цепочки, а не линейное зондированиеШаблон:Sfn.

Дональд КнутШаблон:Sfn суммировал раннюю историю линейного зондирования. Это был первый метод открытой адресации и он был сначала синонимом открытой адресации. Согласно Кнуту, метод первым использовали Джин Амдал, Шаблон:Не переведено 5 и Артур Сэмюэл в 1954 в ассемблерной программе для IBM 701Шаблон:Sfn. Первое опубликованное описание линейного зондирования дал ПетерсонШаблон:SfnШаблон:Sfn, они же упомянули Сэмюэля, Амдала и МакГроу, но добавили, что «система столь естественна, что вполне вероятно, что могла быть независимо создана другими до или в то же время»Шаблон:Sfn. Другая ранняя публикация этого метода принадлежит советскому исследователю Андрею Петровичу Ершову, вышедшая в 1958Шаблон:Sfn.

Первый теоретический анализ линейного зондирования, показывающий, что метод работает за постоянное ожидаемое время на операцию со случайной хеш-функцией, дал КнутШаблон:Sfn. Седжвик назвал работу Кнута «вехой в анализе алгоритмов»Шаблон:Sfn. Существенно позже исследования привели к более детальному анализу распределения вероятностей времени работыШаблон:SfnШаблон:Sfn и доказательство, что линейное зондирование работает за постоянное время на операцию с удобной для практических вычислений хеш-функцией, а не с идеальной случайной функцией, предполагаемой в ранних анализахШаблон:SfnШаблон:Sfn.

Примечания

Шаблон:Примечания

Литература

Шаблон:Refbegin

Шаблон:Refend

Шаблон:Rq

Источник — http://digida.mgpu.ru/index.php?title=Линейное_зондирование&oldid=4671