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