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

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

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

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

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

Операции

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

Поиск

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

Вставка

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

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

Удаление

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

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

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

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

Свойства

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

Анализ

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

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

$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. Эти упрощения приводят к границе

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

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

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

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

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

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

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

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

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

История

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

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

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