Просмотр кода страницы Линейное зондирование

[[Файл:HASHTB12.svg|thumb|upright=1.35|Коллизия между записями «John Smith» и «Sandra Dee» (обе записи имеют хеш-значение 873) разрешается помещением записи «Sandra Dee» на следующее свободное место, ячейку 874.]]
'''Линейное зондирование''' — это схема в [[Программирование|программировании]] для разрешения [[Коллизия хеш-функции|коллизий]] в [[хеш-таблица]]х, [[Структура данных|структурах данных]] для управления наборами {{не переведено 5|Пара атрибут – значение|пар ключ – значение||Attribute–value pair}} и поиска значений, ассоциированных с данным ключом. Схему придумали в 1954 [[Амдал, Джин|Джин Амдал]], {{не переведено 5|Макгроу, Элейн М.|Элейн Макгроу||Elaine M. McGraw}} и [[Сэмюэл, Артур|Артур Сэмюэл]], а проанализировна она была в 1963 [[Кнут, Дональд Эрвин|Дональдом Кнутом]].

Вместе с {{не переведено 5|Квадратичное зондирование|квадратичным зондированием||quadratic probing}} и {{не переведено 5|Двойное зондирование|двойным зондированием||double hashing}} линейное зондирование является видом {{не переведено 5|Открытая адресация|открытой адресации||open addressing}}. В этих схемах каждая ячейка хеш-таблицы содержит одну пару ключ-значение. Если [[Хеширование|хеш-функция]] даёт коллизию, отображая значение нового ключа в ячейку хеш-таблицы, занятую другим ключом, линейное зондирование просматривает таблицу до ближайшей свободной следующей ячейки и вставляет новый ключ туда. Поиск значения осуществляется тем же образом, путём просмотра таблицы последовательно, начиная с позиции, определённой хеш-функцией, пока не найдёт совпадение ключа, либо пустую ячейку.

Как писали Торуп и Чжан, «Хеш-таблицы интенсивно используют нетривиальные структуры данных и большинство имплементаций в аппаратуре использует линейное зондирование, быстрое и простое в реализации»{{sfn|Thorup, Zhang|2012|с=293–331}}.
Линейное зондирование может дать высокую производительность вследствие хорошей {{не переведено 5|Локальность ссылок|локальности ссылок||locality of reference}} метода, но оно более чувствительно к качеству хеш-функции, чем другие схемы разрешения коллизий. Среднее ожидаемое время поиска у метода является константой, то же самое верно для вставки и удаления, если в имплементации используется случайный выбор хеш-функции, {{не переведено 5|K-независимое хеширование|5-независимое хеширование||K-independent hashing}}, или {{не переведено 5|табличное хеширование|||tabulation hashing}}. Однако, на практике, хорошие результаты получаются и с другими функциями хеширования, такими как [[Murmur2|MurmurHash]] {{sfn|Richter, Alvarez, Dittrich|2015|с=293–331}}.

== Операции ==
Линейное зондирование является компонентом схем {{не переведено 5|Открытая адресация|открытой адресации||open addressing}} для использования в [[хеш-таблица]]х для решения [[Ассоциативный массив|словарных задач]]. В словарной задаче структура данных должна работать с набором пар ключ-значение и должна обеспечивать возможность вставки и удаления пар, а также поиск значения, ассоциированного с ключом.
В открытой адресации структурой данных служит [[Массив (программирование)|массив]] {{mvar|T}} (хеш-таблица), ячейки которого {{math|''T''[''i'']}} (если не пусты) содержат единственную пару ключ-значение. [[Хеширование|Хеш-функция]] используется для отображения каждого ключа в ячейку таблицы {{mvar|T}}, куда этот ключ должен быть занесён, как правило, [[Скремблирование|скремблируя]] ключи, так что ключи с близкими значениями не оказываются близко в таблице. [[Коллизия хеш-функции]] возникает, когда хеш-функция отображает ключ в ячейку, уже занятую другим ключом. Линейное зондирование является стратегией для разрешения коллизий путём размещения нового ключа в ближайшую следующую свободную ячейки{{sfn|Goodrich, Tamassia|2015|с=200–203}}{{sfn|Morin|2014|с=108–116}}.

=== Поиск ===
Для поиска заданного ключа {{mvar|x}} проверяются ячейки таблицы {{mvar|T}}, начиная с ячейки с индексом {{math|''h''(''x'')}} (где {{mvar|h}} — хеш-функция), затем ячейки {{math|''h''(''x'') + 1}}, {{math|''h''(''x'') + 2}}, …, пока не будет найдена [[свободная ячейка]] или ячейка, в которой содержится ключ {{mvar|x}}.
Если ячейка, содержащая ключ, найдена, процедура поиска возвращает значение из этой ячейки. В противном случае, если встретилась пустая ячейка, ключ не может находиться в таблице и процедура возвращает в качестве результата, что ключ не найден{{sfn|Goodrich, Tamassia|2015|с=200–203}}{{sfn|Morin|2014|с=108–116}}

=== Вставка ===
Для вставки пары ключ-значение {{math|(''x'',''v'')}} в таблицу (возможно, с заменой любой существующей пары с тем же ключом) алгоритм вставки проходит ту же последовательность ячеек, что и при поиске, пока не найдёт либо пустую ячейку, либо ячейку, содержащую ключ {{mvar|x}}.
Новая пара ключ-значение размещается в этой ячейке{{sfn|Goodrich, Tamassia|2015|с=200–203}}{{sfn|Morin|2014|с=108–116}}.

Если после вставки [[Хеш-таблица|коэффициент загрузки]] таблицы (доля занятых ячеек) превышает некоторый порог, вся таблица может быть заменена на новую таблицу, размер которой увеличивается на постоянный множитель, как в случае [[Динамический массив|динамического массива]], с новой хеш-таблицей. Установка этого порога близким к нулю и использование высокого коэффициента расширения таблицы приводит к быстрым операциям, но требует больших затрат памяти. Обычно размер таблицы удваивается при достижении коэффициента загрузки 1/2, так что загрузка составляет от 1/4 до 1/2<ref>{{harvnb|Sedgewick, Wayne|2011|с=471 }}; Седжвик и Уэйн уменьшают вдвое размер таблицы, если при делении загрузка таблицы станет слишком низкой, что приводит к более широкому диапазону [1/8,1/2] возможных значений коэффициента загрузки.</ref>

=== Удаление ===
[[Файл:Linear Probing Deletion.png|thumb|upright=2.5|Когда удаляется пара ключ-значение, может оказаться необходимым перенести другую пару в эту ячейку, чтобы избежать получение пустой ячейки при поиске удалённого ключа]]
Можно удалить пару ключ-значение из словаря. Однако недостаточно просто очистить ячейку. Возможно, существует другая пара с тем же хеш-значением, которая была размещена где-то после занятой ячейки. После очистки ячейки поиск второго значения с тем же значением хеш-функции наткнётся на пустую ячейку, и пара не будет найдена.

Таким образом, при очистке ячейки {{mvar|i}} необходимо просмотреть последующие ячейки, пока не найдём пустую ячейку, либо ключ, который можно перенести в ячейку {{mvar|i}} (то есть ключ, хеш-значение которого равно или меньше {{mvar|i}}). Если найдена пустая ячейка, то можно очистить ячейку {{mvar|i}} и остановить процесс удаления. Если же найден ключ, который можно перенести в ячейку {{mvar|i}}, переносим его. Это приведёт к увеличению скорости поиска перенесённого ключа, а также очищает другую ячейку в блоке занятых ячеек. Необходимо продолжить поиск ключа, который может быть перенесён на это освободившееся место. Поиск ключа для переноса осуществляется до пустой ячейки, пока не достигнем ячейки, которая изначально была пуста. Таким образом, время выполнения всего процесса удаления пропорционально длине блока, содержащего удалённый ключ{{sfn|Goodrich, Tamassia|2015|с=200–203}}.

Альтернативно, можно использовать стратегию {{не переведено 5|Ленивое удаление|ленивого удаления||lazy deletion}}, в которой пара ключ-значение удаляется путём замены значения специальным {{не переведено 5|Контрольное значение|флагом||Sentinel value}}, показывающим, что ключ удалён. Однако такие флаги приводят к увеличению коэффициента загрузки хеш-таблицы. В этой стратегии может стать необходимым удалить флаги из массива и пересчитать хеш-значения всех оставшихся пар ключ-значение, когда слишком много значений окажутся удалёнными{{sfn|Goodrich, Tamassia|2015|с=200–203}}{{sfn|Morin|2014|с=108–116}}.

== Свойства ==
Линейное зондирование даёт хорошую {{не переведено 5|Локальность ссылок|локальность ссылок||locality of reference}}, что означает, что нужно лишь несколько некешированных операций доступа к память на одну операцию. Ввиду этого, при поддержке низкого коэффициента загрузки алгоритм может дать высокую степень производительности. Однако, по сравнению с некоторыми другими стратегиями открытой адресации, скорость работы деградирует быстрее при высокой степени загрузки ввиду {{не переведено 5|Первичная кластеризация|первичной кластеризации||primary clustering}}, тенденции одной коллизии вызывать много близких коллизий {{sfn|Goodrich, Tamassia|2015|с=200–203}}. Кроме того, для получения хорошей скорости работы этого метода требуется хеш-функция более высокого качества, чем для других схем разрешения коллизий{{sfn|Pătraşcu, Thorup|2010|с=715–726}}. Если алгоритм реализуется с хеш-функцией низкого качества, которая не исключает неоднородности во входном распределении, линейное зондирование может оказаться медленнее других стратегий открытой адресации, таких как {{не переведено 5|Двойное зондирование|двойное зондирование||double hashing}}, которое пробует последовательность ячеек, разъединение которых определяется второй хеш-функцией, или {{не переведено 5|Квадратичное зондирование|квадратичное зондирование||quadratic probing}}, когда размер каждого шага меняется в зависимости от позиции в последовательности проб{{sfn|Heileman, Luo|2005|с=141–154}}.

== Анализ ==
При использовании линейного зондирования операции со словарём могут быть имплементированы с постоянным [[Сложность алгоритма в среднем|ожидаемым временем]] доступа. Другими словами, операции вставки, удаления и поиска могут быть имплементированы за [[«O» большое и «o» малое|O(1)]], при условии, что [[Хеш-таблица|коэффициент загрузки]] хеш-таблицы является константой, строго меньшей единицы{{sfn|Knuth|1963}}.

Подробнее, время для каждой отдельной операции (поиск, вставка или удаление) пропорционально длине непрерывного блока занятых ячеек, с которого операция начинается. Если все начальные ячейки равновозможны в хеш-таблице с {{mvar|N}} ячейками, то максимальный блок {{mvar|k}} занятых ячеек имеет вероятность {{math|''k''/''N''}} содержать начальное положение поиска и займёт время {{math|''O''(''k'')}}, где бы ни находилась стартовая ячейка. Таким образом, ожидаемое время выполнения операции можно вычислить как произведение этих двух членов, {{math|''O''(''k''<sup>2</sup>/''N'')}}, суммированных по всем максимальным блокам непрерывных ячеек в таблице. Похожая сумма квадратов длин блоков дают границу мат. ожидания времени для случайной хеш-функции (а не случайное стартовое положение в хеш-таблице) путём суммирования по всем блокам, которые могут существовать (а не по тем, которые фактически существуют в текущем состоянии таблицы) и умножения членов для каждого потенциального блока на вероятность, что блок занят. То есть, если определить {{math|Block(''i'',''k'')}} как событие, что имеется максимальный непрерывный блок занятых ячеек длины {{mvar|k}}, начинающийся с индекса {{mvar|i}}, мат. ожидание времени на операцию равно
: <math>E[T]=O(1) + \sum_{i=1}^N \sum_{k=1}^n O(k^2/N) \operatorname{Pr}[\operatorname{Block}(i,k)].</math>
Формулу можно упростить путём замены {{math|Block(''i'',''k'')}} by a simpler necessary condition {{math|Full(''k'')}}, the event that at least {{mvar|k}} elements have hash values that lie within a block of cells of length {{mvar|k}}. After this replacement, the value within the sum no longer depends on {{mvar|i}}, and the {{math|1/''N''}} factor cancels the {{mvar|N}} terms of the outer summation. Эти упрощения приводят к границе
: <math>E[T] \le O(1) + \sum_{k=1}^n O(k^2) \operatorname{Pr}[\operatorname{Full}(k)].</math>
Но, согласно мультипликативной форме [[Граница Чернова|границы Чернова]], если коэффициент загрузки строго меньше единицы, вероятность, что длина блока {{mvar|k}} содержит по меньшей мере {{mvar|k}} хешированных значений, является экспоненциально малой как функция от {{mvar|k}}, что означает, что сумма ограничена константой, не зависящей от {{mvar|n}}{{sfn|Goodrich, Tamassia|2015|с=200–203}}. Можно также провести тот же анализ с помощью [[Формула Стирлинга|формулы Стирлинга]] вместо границы Чернова, чтобы оценить вероятность того, что блок содержит в точности {{mvar|k}} хешированных значений{{sfn|Morin|2014|с=108–116}}{{sfn|Eppstein|2011}}.

В терминах коэффициента загрузки {{mvar|&alpha;}} ожидаемое время успешного поиска равно {{math|''O''(1 + 1/(1 − ''&alpha;''))}}, а ожидаемое время неуспешного поиска (или вставки нового ключа) равно {{math|''O''(1 + 1/(1 − ''&alpha;'')<sup>2</sup>)}} {{sfn|Sedgewick|2003}}.
Для постоянного коэффициента загрузки, с большой вероятностью, самая длинная последовательность зондирования (среди последовательностей зондирования для всех ключей из таблицы) имеет логарифмическую длину{{sfn|Pittel|1987|с=236–249}}.

== Выбор Хеш-функции ==
Поскольку линейное зондирование очень чувствительно для неравномерно распределённых значений хеш-функций{{sfn|Heileman, Luo|2005|с=141–154}}, важно комбинировать метод с хеш-функцией высокого качества, которая не даёт такую неравномерность.

Анализ, приведённый выше, предполагает, что хеш каждого ключа является случайным числом, не зависящим от хешей других ключей. Это предположение нереалистично для большинства приложений с хешированием.
Однако случайные или [[Псевдослучайное число|псевдослучайные]] хеш-значения могут быть использованы, когда объекты хешируются по их идентификатору, а не по значению. Например, так сделано с использованием линейного зондирования с помощью класса IdentityHashMap в наборе классов и интерфейсов [[Java collections framework]]{{sfn|Java SE 7 Documentation}}.
Значение хеша, который этот класс ассоциирует с каждым объектом, его identityHashCode, гарантированно остаётся неизменным для объекта на протяжении его жизни, но хеш-значение для такого же объекта в других обстоятельствах будет другим{{sfn|Friesen|2012|с=376}}. Поскольку identityHashCode строится только раз для каждого объекта и не требуется его связь со значением или адресом объекта, его построение может использовать более медленные вычислительные средства, такие как вызов случайных или псевдослучайных генераторов чисел. Например, Java 8 для построения таких значений использует псевдослучайный числовой генератор [[Xorshift]]{{sfn|Kabutz|2014}}.

Для большинства приложений хеширования необходимо вычислять хеш-функцию для каждого значения каждый раз, когда требуется хеш, а не один раз, когда объект создаётся. В таких приложениях случайные или псевдослучайные числа не могут быть использованы в качестве хеш-значений, поскольку тогда различные объекты с тем же значением могли бы иметь различные значения хеша. А [[Криптографическая хеш-функция|криптографические хеш-функции]] (которые создаются так, что они неотличимы от истинно случайных функций) обычно слишком медленны для использования в хеш-таблицах{{sfn|Weiss|2014|с=3—11}}. Вместо этого используются другие методы для построения хеш-функций. Эти методы вычисляют хеш-функцию быстро, и можно доказать, что они хорошо работают с линейным зондированием. В частности, линейное зондирование было проанализировано в рамках {{не переведено 5|K-независимое хеширование|{{mvar|k}}-независимого хеширования||K-independent hashing}}, классе хеш-функций, которые инициализируются небольшим случайным числом с равной возможностью отображают любой {{mvar|k}}-кортеж различных ключей в любой {{mvar|k}}-кортеж индексов. Параметр {{mvar|k}} может рассматриваться как мера качества хеш-функции — чем больше {{mvar|k}}, тем больше времени нужно для вычисления хеш-функции, но она будет вести себя ближе к полностью случайным функциям.
Для линейного зондирования 5-независимость достаточна, чтобы гарантировать постоянное ожидаемое время на операцию{{sfn|Pagh, Pagh, Ružić|2009|с=1107–1120}}, в то время как некоторые 4-независимые хеш-функции работают плохо, требуя логарифмического времени на операцию{{sfn|Pătraşcu, Thorup|2010|с=715–726}}.
 
Другой метод построения хеш-функций с высоким качеством и приемлемой скоростью — {{не переведено 5|табличное хеширование|||tabulation hashing}}. В этом методе значение хеша для ключа вычисляется путём выбора для каждого байта ключа индекса в таблице случайных чисел (с различными таблицами для каждой позиции байта). Числа из ячеек этих таблиц затем комбинируются побитно с помощью операции [[Сложение по модулю 2|«исключающее ИЛИ»]]. Хеш-функции, построенные таким образом, только 3-независимы. Тем не менее, линейные зондирования, использующие эти хеш-функции, требуют постоянного ожидаемого времени на операцию{{sfn|Morin|2014|с=108–116}}{{sfn|Pătrașcu, Thorup|2011|с= 1–10}}. Как табличное хеширование, так и стандартные методы генерации 5-независимых хеш-функций лимитированы ключами, которые имеют фиксированное число бит. Для работы со [[Строковый тип|строками]] или другими типами ключей переменной длины, можно {{не переведено 5|Композиция функций (информатика)|скомбинировать||compose}} более простую технику [[Универсальное хеширование|универсального хеширования]], которая отображает ключи в промежуточные значения, с высокого качества (5-независимость или [[табуляция]]) хеш-функцией, которая отображает промежуточные значения в индексы хеш-таблицы{{sfn|Thorup, Zhang|2012|с=293–331}}{{sfn|Thorup|2009|с=655–664}}.

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

== История ==
Идея [[Ассоциативный массив|ассоциативного массива]], которая позволяет получить доступ к данным по их значению, а не через их адрес, восходит к середине 1940-х годов к работам [[Цузе, Конрад|Конрада Цузе]] и [[Буш, Вэнивар|Вэнивара Буша]]{{sfn|Parhami|2006|с=67}}, но хеш-таблицы не были описаны, пока их не описал {{не переведено 5|Лун, Ганс Питер|Лун||Hans Peter Luhn}} в меморандуме [[IBM]] в 1953. Лун использовал другой метод разрешения коллизий, связь в цепочки, а не линейное зондирование{{sfn|Morin|2004|с=9—15}}.

Дональд Кнут{{sfn|Knuth|1963}} суммировал раннюю историю линейного зондирования. Это был первый метод открытой адресации и он был сначала синонимом открытой адресации. Согласно Кнуту, метод первым использовали [[Амдал, Джин|Джин Амдал]], {{не переведено 5|МакГроу, Элани М.|||Elaine M. McGraw}} и [[Сэмюэл, Артур|Артур Сэмюэл]] в 1954 в [[Язык ассемблера|ассемблерной]] программе для [[IBM 701]]{{sfn|Knuth|1963}}. Первое опубликованное описание линейного зондирования дал Петерсон{{sfn|Peterson|1957}}{{sfn|Knuth|1963}}, они же упомянули Сэмюэля, Амдала и МакГроу, но добавили, что «система столь естественна, что вполне вероятно, что могла быть независимо создана другими до или в то же время»{{sfn|Peterson|1957|с=130–146}}. Другая ранняя публикация этого метода принадлежит советскому исследователю [[Ершов, Андрей Петрович|Андрею Петровичу Ершову]], вышедшая в 1958{{sfn|Ершов|1958|с= 3–6}}.

Первый теоретический анализ линейного зондирования, показывающий, что метод работает за постоянное ожидаемое время на операцию со случайной хеш-функцией, дал Кнут{{sfn|Knuth|1963}}. [[Седжвик, Роберт|Седжвик]] назвал работу Кнута «вехой в анализе алгоритмов»{{sfn|Sedgewick|2003}}. Существенно позже исследования привели к более детальному анализу [[Распределение вероятностей|распределения вероятностей]] времени работы{{sfn|Flajolet, Poblete, Viola|1998|с=490–515}}{{sfn|Knuth|1998|с=561–568}} и доказательство, что линейное зондирование работает за постоянное время на операцию с удобной для практических вычислений хеш-функцией, а не с идеальной случайной функцией, предполагаемой в ранних анализах{{sfn|Pagh, Pagh, Ružić|2009|с=1107–1120}}{{sfn|Pătrașcu, Thorup|2011|с= 1–10}}.

== Примечания ==
{{примечания|25em}}

== Литература ==
{{refbegin|colwidth=45em}}
* {{статья
|автор=David Eppstein
|ref=Eppstein
|заглавие=Linear probing made easy
|месяц=October
|год=2011
}}
* {{статья
|автор=[[Кнут, Дональд Эрвин|Donald Knuth]]
|ref=Knuth
|заглавие=Notes on "Open" Addressing
|год=1963
|ссылка= http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=27DC9AB829BC9A3202CFD007858055E8?doi=10.1.1.56.4899&rep=rep1&type=pdf
}}
* {{книга
|заглавие=Proceedings of the Seventh Workshop on Algorithm Engineering and Experiments and the Second Workshop on Analytic Algorithmics and Combinatorics 
|часть=How caching affects hashing
|автор=Gregory L. Heileman, Wenbin Luo
|ref=Heileman, Luo
|ссылка=http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf
|год=2005
|страницы=141–154
|издательство=Society for Industrial & Applied Mathematics,U.S.
|ISBN=0898715962
}}
* {{книга
|часть=Section 6.3.3: Linear Probing
|страницы=200–203
|заглавие=Algorithm Design and Applications
|автор=Michael T. Goodrich, Roberto Tamassia
|ref=Goodrich, Tamassia
|издательство=Wiley
|isbn=978-1-118-33591-8
|год=2015
}}
* {{книга
|часть=Section 14.3: Linear Probing
|страницы=615–620
|заглавие=Algorithms in Java, Parts 1–4: Fundamentals, Data Structures, Sorting, Searching
|edition=3rd
|автор=Robert Sedgewick
|ref=Sedgewick
|издательство=Addison Wesley
|год=2003
|isbn=9780321623973
}}
* {{книга
|заглавие=Алгоритмы
|издание=4th
|автор=Robert Sedgewick, Kevin Wayne
|ref=Sedgewick, Wayne
|издательство=Addison-Wesley Professional
|год=2011
|isbn=9780321573513
|ссылка=https://books.google.com/books?id=MTpsAQAAQBAJ&pg=PA471
}}
* {{статья
|автор=Pittel B.
|ref=Pittel
|doi=10.1016/0196-6774(87)90040-X
|выпуск=2
|издание=Journal of Algorithms
|mr=890874
|страницы=236–249
|заглавие=Linear probing: the probable largest search time grows logarithmically with the number of records
|том=8
|год=1987
}}
* {{cite web
|url=https://docs.oracle.com/javase/7/docs/api/java/util/IdentityHashMap.html
|title=IdentityHashMap
|ref=Java SE 7 Documentation
|publisher=Oracle
|accessdate=2016-01-15
}}
* {{книга
|заглавие=Beginning Java 7
|серия=Expert's voice in Java
|автор=Jeff Friesen
|ref=Friesen
|издательство=Apress
|год=2012
|isbn=9781430239109
|страницы=376
|ссылка=https://books.google.com/books?id=CwSaQpCtfPkC&pg=PA376
}}
* {{статья
|ссылка=http://www.javaspecialists.eu/archive/Issue222.html
|заглавие=Identity Crisis
|автор=Heinz M. Kabutz
|ref=Kabutz
|издание=The Java Specialists' Newsletter
|том=222
|месяц=September
|год=2014
}}
* {{книга
|заглавие=Computing Handbook
|издание=3rd
|том=1
|ответственныйt=Teofilo Gonzalez, Jorge Diaz-Herrera, Allen Tucker
|издательство=CRC Press
|год=2014
|isbn=9781439898536
|автор=Mark Allen Weiss
|ref=Weiss
|часть=Chapter 3: Data Structures
|страницы=3—11
|ссылка=https://books.google.com/books?id=wyHSBQAAQBAJ&pg=SA3-PA11
}}
* {{книга
|автор=Pat Morin
|ref=Morin
|часть=Section 5.2: LinearHashTable: Linear Probing
|страницы=108–116
|заглавие=Open Data Structures (in pseudocode)
|edition=0.1G''&beta;''
|ссылка=http://opendatastructures.org/
|месяц=February
|год=2014
|accessdate=2016-01-15
}}
* {{статья
|автор=Anna Pagh, Rasmus Pagh, Milan Ružić
|ref=Pagh, Pagh, Ružić
|doi=10.1137/070702278
|выпуск=3
|издание=[[SIAM Journal on Computing]]
|mr=2538852
|страницы=1107–1120
|заглавие=Linear probing with constant independence
|том=39
|год=2009
}}
* {{книга
|автор=Mihai Pătrașcu, Mikkel Thorup
|ref=Pătraşcu, Thorup
|часть=On the {{mvar|k}}-independence required by linear probing and minwise independence
|doi=10.1007/978-3-642-14165-2_60
|страницы=715–726
|издательство=Springer
|серия=[[Lecture Notes in Computer Science]]
|заглавие=[[International Colloquium on Automata, Languages and Programming|Automata, Languages and Programming]], 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6–10, 2010, Proceedings, Part I
|ссылка=http://people.csail.mit.edu/mip/papers/kwise-lb/kwise-lb.pdf
|том=6198
|год=2010
}}
* {{книга
|автор=Mihai Pătrașcu, Mikkel Thorup
|ref=Pătrașcu, Thorup
|arxiv=1011.5200
|часть=The power of simple tabulation hashing
|doi=10.1145/1993636.1993638
|страницы=1–10
|заглавие=Proceedings of the 43rd annual ACM [[Symposium on Theory of Computing]] (STOC '11)
|год=2011
}}
* {{статья
|автор=Mikkel Thorup, Yin Zhang
|ref=Thorup, Zhang
|doi=10.1137/100800774
|выпуск=2
|издание=SIAM Journal on Computing
|mr=2914329
|страницы=293–331
|заглавие=Tabulation-based 5-independent hashing with applications to linear probing and second moment estimation
|том=41
|год=2012
}}
* {{книга
|ref=Thorup
|автор=Mikkel Thorup
|часть=String hashing for linear probing
|doi=10.1137/1.9781611973068.72
|место=Philadelphia, PA
|mr=2809270
|страницы=655–664
|издательство=SIAM
|заглавие=Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms
|год=2009
}}
* {{статья
|автор=Stefan  Richter, Victor Alvarez, Jens Dittrich
|ref=Richter, Alvarez, Dittrich
|выпуск=3
|издание=Proceedings of the VLDB Endowment
|страницы=293–331
|заглавие=A seven-dimensional analysis of hashing methods and its implications on query processing
|том=9
|год=2015
}}
* {{книга
|заглавие=Introduction to Parallel Processing: Algorithms and Architectures
|серия=Series in Computer Science
|автор=Behrooz Parhami
|ref=Parhami
|издательство=Springer
|год=2006
|isbn=9780306469640
|страницы=67 4.1 Development of early models
|ссылка=https://books.google.com/books?id=iNQLBwAAQBAJ&pg=PA67
}}
* {{книга
|заглавие=Handbook of Data Structures and Applications
|страницы=9—15
|isbn=9781420035179
|ответственный=Dinesh P. Mehta, Sartaj Sahni
|часть=Hash tables
|автор=Pat Morin
|ref=Morin
|ссылка=https://books.google.com/books?id=fQVZy1zcpJkC&pg=SA9-PA15
|год=2004
|издательство=Chapman & Hall / CRC
}}
* {{статья
|автор=Peterson W. W.
|ref=Peterson
|месяц=April
|год=1957
|doi=10.1147/rd.12.0130
|выпуск=2
|издание=[[IBM Journal of Research and Development]]
|место=Riverton, NJ, USA
|страницы=130–146
|издательство=IBM Corp.
|заглавие=Addressing for random-access storage
|том=1
}}. Другая ранняя публикация этого метода принадлежит советскому исследователю [[Ершов, Андрей Петрович|Ершову А. П.]], in 1958.
* {{статья
|автор=А. П. Ершов
|ref=Ершов
|издание=Доклады АН УССР
|выпуск=118 (3)
|страницы=427–430
|год=1958
}}. Линейное зондирование описано как алгоритм A2.
* {{статья
|автор=Flajolet P., Poblete P., Viola A.
|ref=Flajolet, Poblete, Viola
|doi=10.1007/PL00009236
|выпуск=4
|издание=[[Algorithmica]]
|mr=1701625
|страницы=490–515
|заглавие=On the analysis of linear probing hashing
|том=22
|год=1998
}}
* {{статья
|автор=[[Кнут, Дональд Эрвин|Donald Knuth]]
|ref=Knuth
|doi=10.1007/PL00009240
|выпуск=4
|издание=[[Algorithmica]]
|mr=1701629
|страницы=561–568
|заглавие=Linear probing and graphs
|том=22
|год=1998
}}
{{refend}}

{{rq|checktranslate|style}}

[[Категория:Хеширование]]
[[Категория:Алгоритмы поиска]]