Линейное зондирование — схема в программировании для разрешения коллизий в хеш-таблицах, структурах данных для управления наборами и поиска значений, ассоциированных с данным ключом. Схему придумали в 1954 Джин Амдал, и Артур Сэмюэл (и независимо Андрей Ершов ), а проанализирована она была в 1963 Дональдом Кнутом.
Вместе с и линейное зондирование является видом . В этих схемах каждая ячейка хеш-таблицы содержит одну пару ключ-значение. Если хеш-функция даёт коллизию, отображая значение нового ключа в ячейку хеш-таблицы, занятую другим ключом, линейное зондирование просматривает таблицу до ближайшей свободной следующей ячейки и вставляет новый ключ туда. Поиск значения осуществляется тем же образом, путём просмотра таблицы последовательно, начиная с позиции, определённой хеш-функцией, пока не найдёт совпадение ключа, либо пустую ячейку.
Как писали Торуп и Чжан, «Хеш-таблицы интенсивно используют нетривиальные структуры данных и большинство имплементаций в аппаратуре использует линейное зондирование, быстрое и простое в реализации». Линейное зондирование может дать высокую производительность вследствие хорошей метода, но оно более чувствительно к качеству хеш-функции, чем другие схемы разрешения коллизий. Среднее ожидаемое время поиска у метода является константой, то же самое верно для вставки и удаления, если в имплементации используется случайный выбор хеш-функции, , или . Однако, на практике, хорошие результаты получаются и с другими функциями хеширования, такими как MurmurHash .
Операции Линейное зондирование является компонентом схем для использования в хеш-таблицах для решения словарных задач. В словарной задаче структура данных должна работать с набором пар ключ-значение и должна обеспечивать возможность вставки и удаления пар, а также поиск значения, ассоциированного с ключом. В открытой адресации структурой данных служит массив (хеш-таблица), ячейки которого (если не пусты) содержат единственную пару ключ-значение. Хеш-функция используется для отображения каждого ключа в ячейку таблицы , куда этот ключ должен быть занесён, как правило, скремблируя ключи, так что ключи с близкими значениями не оказываются близко в таблице. Коллизия хеш-функции возникает, когда хеш-функция отображает ключ в ячейку, уже занятую другим ключом. Линейное зондирование является стратегией для разрешения коллизий путём размещения нового ключа в ближайшую следующую свободную ячейки.
Поиск Для поиска заданного ключа проверяются ячейки таблицы , начиная с ячейки с индексом (где — хеш-функция), затем ячейки , , …, пока не будет найдена свободная ячейка или ячейка, в которой содержится ключ . Если ячейка, содержащая ключ, найдена, процедура поиска возвращает значение из этой ячейки. В противном случае, если встретилась пустая ячейка, ключ не может находиться в таблице и процедура возвращает в качестве результата, что ключ не найден
Вставка Для вставки пары ключ-значение в таблицу (возможно, с заменой любой существующей пары с тем же ключом) алгоритм вставки проходит ту же последовательность ячеек, что и при поиске, пока не найдёт либо пустую ячейку, либо ячейку, содержащую ключ . Новая пара ключ-значение размещается в этой ячейке.
Если после вставки коэффициент загрузки таблицы (доля занятых ячеек) превышает некоторый порог, вся таблица может быть заменена на новую таблицу, размер которой увеличивается на постоянный множитель, как в случае динамического массива, с новой хеш-таблицей. Установка этого порога близким к нулю и использование высокого коэффициента расширения таблицы приводит к быстрым операциям, но требует больших затрат памяти. Обычно размер таблицы удваивается при достижении коэффициента загрузки 1/2, так что загрузка составляет от 1/4 до 1/2; Седжвик и Уэйн уменьшают вдвое размер таблицы, если при делении загрузка таблицы станет слишком низкой, что приводит к более широкому диапазону [1/8,1/2] возможных значений коэффициента загрузки.
Удаление
Можно удалить пару ключ-значение из словаря. Однако недостаточно просто очистить ячейку. Возможно, существует другая пара с тем же хеш-значением, которая была размещена где-то после занятой ячейки. После очистки ячейки поиск второго значения с тем же значением хеш-функции наткнётся на пустую ячейку, и пара не будет найдена.
Таким образом, при очистке ячейки необходимо просмотреть последующие ячейки, пока не найдём пустую ячейку, либо ключ, который можно перенести в ячейку (то есть ключ, хеш-значение которого равно или меньше ). Если найдена пустая ячейка, то можно очистить ячейку и остановить процесс удаления. Если же найден ключ, который можно перенести в ячейку , переносим его. Это приведёт к увеличению скорости поиска перенесённого ключа, а также очищает другую ячейку в блоке занятых ячеек. Необходимо продолжить поиск ключа, который может быть перенесён на это освободившееся место. Поиск ключа для переноса осуществляется до пустой ячейки, пока не достигнем ячейки, которая изначально была пуста. Таким образом, время выполнения всего процесса удаления пропорционально длине блока, содержащего удалённый ключ.
Альтернативно, можно использовать стратегию , в которой пара ключ-значение удаляется путём замены значения специальным , показывающим, что ключ удалён. Однако такие флаги приводят к увеличению коэффициента загрузки хеш-таблицы. В этой стратегии может стать необходимым удалить флаги из массива и пересчитать хеш-значения всех оставшихся пар ключ-значение, когда слишком много значений окажутся удалёнными.
Свойства Линейное зондирование даёт хорошую , что означает, что нужно лишь несколько некешированных операций доступа к память на одну операцию. Ввиду этого, при поддержке низкого коэффициента загрузки алгоритм может дать высокую степень производительности. Однако, по сравнению с некоторыми другими стратегиями открытой адресации, скорость работы деградирует быстрее при высокой степени загрузки ввиду , тенденции одной коллизии вызывать много близких коллизий . Кроме того, для получения хорошей скорости работы этого метода требуется хеш-функция более высокого качества, чем для других схем разрешения коллизий. Если алгоритм реализуется с хеш-функцией низкого качества, которая не исключает неоднородности во входном распределении, линейное зондирование может оказаться медленнее других стратегий открытой адресации, таких как , которое пробует последовательность ячеек, разъединение которых определяется второй хеш-функцией, или , когда размер каждого шага меняется в зависимости от позиции в последовательности проб.
Анализ При использовании линейного зондирования операции со словарём могут быть имплементированы с постоянным ожидаемым временем доступа. Другими словами, операции вставки, удаления и поиска могут быть имплементированы за O(1), при условии, что коэффициент загрузки хеш-таблицы является константой, строго меньшей единицы.
Подробнее, время для каждой отдельной операции (поиск, вставка или удаление) пропорционально длине непрерывного блока занятых ячеек, с которого операция начинается. Если все начальные ячейки равновозможны в хеш-таблице с ячейками, то максимальный блок занятых ячеек имеет вероятность содержать начальное положение поиска и займёт время , где бы ни находилась стартовая ячейка. Таким образом, ожидаемое время выполнения операции можно вычислить как произведение этих двух членов, , суммированных по всем максимальным блокам непрерывных ячеек в таблице. Похожая сумма квадратов длин блоков дают границу мат. ожидания времени для случайной хеш-функции (а не случайное стартовое положение в хеш-таблице) путём суммирования по всем блокам, которые могут существовать (а не по тем, которые фактически существуют в текущем состоянии таблицы) и умножения членов для каждого потенциального блока на вероятность, что блок занят. То есть, если определить как событие, что имеется максимальный непрерывный блок занятых ячеек длины , начинающийся с индекса , мат. ожидание времени на операцию равно
Формулу можно упростить путём замены by a simpler necessary condition , the event that at least elements have hash values that lie within a block of cells of length . After this replacement, the value within the sum no longer depends on , and the factor cancels the terms of the outer summation. Эти упрощения приводят к границе
Но, согласно мультипликативной форме границы Чернова, если коэффициент загрузки строго меньше единицы, вероятность, что длина блока содержит по меньшей мере хешированных значений, является экспоненциально малой как функция от , что означает, что сумма ограничена константой, не зависящей от . Можно также провести тот же анализ с помощью формулы Стирлинга вместо границы Чернова, чтобы оценить вероятность того, что блок содержит в точности хешированных значений.
В терминах коэффициента загрузки ожидаемое время успешного поиска равно , а ожидаемое время неуспешного поиска (или вставки нового ключа) равно . Для постоянного коэффициента загрузки, с большой вероятностью, самая длинная последовательность зондирования (среди последовательностей зондирования для всех ключей из таблицы) имеет логарифмическую длину.
Выбор хеш-функции Поскольку линейное зондирование очень чувствительно для неравномерно распределённых значений хеш-функций, важно комбинировать метод с хеш-функцией высокого качества, которая не даёт такую неравномерность.
Анализ, приведённый выше, предполагает, что хеш каждого ключа является случайным числом, не зависящим от хешей других ключей. Это предположение нереалистично для большинства приложений с хешированием. Однако случайные или псевдослучайные хеш-значения могут быть использованы, когда объекты хешируются по их идентификатору, а не по значению. Например, так сделано с использованием линейного зондирования с помощью класса IdentityHashMap в наборе классов и интерфейсов Java collections framework. Значение хеша, который этот класс ассоциирует с каждым объектом, его identityHashCode, гарантированно остаётся неизменным для объекта на протяжении его жизни, но хеш-значение для такого же объекта в других обстоятельствах будет другим. Поскольку identityHashCode строится только раз для каждого объекта и не требуется его связь со значением или адресом объекта, его построение может использовать более медленные вычислительные средства, такие как вызов случайных или псевдослучайных генераторов чисел. Например, Java 8 для построения таких значений использует псевдослучайный числовой генератор Xorshift.
Для большинства приложений хеширования необходимо вычислять хеш-функцию для каждого значения каждый раз, когда требуется хеш, а не один раз, когда объект создаётся. В таких приложениях случайные или псевдослучайные числа не могут быть использованы в качестве хеш-значений, поскольку тогда различные объекты с тем же значением могли бы иметь различные значения хеша. А криптографические хеш-функции (которые создаются так, что они неотличимы от истинно случайных функций) обычно слишком медленны для использования в хеш-таблицах. Вместо этого используются другие методы для построения хеш-функций. Эти методы вычисляют хеш-функцию быстро, и можно доказать, что они хорошо работают с линейным зондированием. В частности, линейное зондирование было проанализировано в рамках , классе хеш-функций, которые инициализируются небольшим случайным числом с равной возможностью отображают любой -кортеж различных ключей в любой -кортеж индексов. Параметр может рассматриваться как мера качества хеш-функции — чем больше , тем больше времени нужно для вычисления хеш-функции, но она будет вести себя ближе к полностью случайным функциям. Для линейного зондирования 5-независимость достаточна, чтобы гарантировать постоянное ожидаемое время на операцию, в то время как некоторые 4-независимые хеш-функции работают плохо, требуя логарифмического времени на операцию.