Введение

Метод компьютерного программирования для хеширования

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

Поиск

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

Удаление

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

Первичное кластерирование

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

История

Идея ассоциативного массива, позволяющего получать доступ к данным по их значению, а не по адресу, восходит к середине 1940-х годов в работах Конрада Цузе и Ванневара Буша, но хэш-таблицы были описаны только в 1953 году в меморандуме IBM Ханса Петера Луна. Лун использовал другой метод разрешения коллизий – цепное связывание, а не линейное зондирование. Обобщает раннюю историю линейного зондирования. Это был первый метод открытой адресации и первоначально являлся синонимом открытой адресации. Согласно Кнуту, он был впервые использован Джином Амдалем, Элейн М. Макгроу (урождённой Боем) и Артуром Сэмюэлем в 1954 году в программе-ассемблере для компьютера IBM 701. Еще одна ранняя публикация этого метода принадлежит советскому исследователю Андрею Ершову, в 1958 году. Первый теоретический анализ линейного зондирования, показавший, что оно требует постоянного среднего времени на операцию при использовании случайных хеш-функций, был представлен Кнутом. Также было доказано, что линейное зондирование выполняется за постоянное время на операцию с практически применимыми хеш-функциями, в отличие от идеализированных случайных функций, использовавшихся в более ранних анализах.