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

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