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

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

Удаление

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

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

Таким образом, при очистке ячейки 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) by a simpler necessary condition Full(k), the event that at least k elements have hash values that lie within a block of cells of length k. After this replacement, the value within the sum no longer depends on i, and the 1/N factor cancels the N terms of the outer summation. Эти упрощения приводят к границе

${\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 collections framework[12]. Значение хеша, который этот класс ассоциирует с каждым объектом, его identityHashCode, гарантированно остаётся неизменным для объекта на протяжении его жизни, но хеш-значение для такого же объекта в других обстоятельствах будет другим[13]. Поскольку identityHashCode строится только раз для каждого объекта и не требуется его связь со значением или адресом объекта, его построение может использовать более медленные вычислительные средства, такие как вызов случайных или псевдослучайных генераторов чисел. Например, Java 8 для построения таких значений использует псевдослучайный числовой генератор Xorshift[14].

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

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

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

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

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

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