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

Cтраница 1

Линейное зондирование с увеличением путем удвоения используется во всех случаях, когда операция insert приводит к тому, что количество ключей в таблице становится равным половине размера таблицы. Сужение путем уменьшения размера таблицы вдвое используется, когда операция remove приводит к тому, что количество ключей в таблице становится равным одной восьмой размера таблицы. В обоих случаях после того, как размер таблицы изменен до значения N, она содержит 7V / 4 ключей. В обоих случаях количество повторно вставляемых ключей не превышает двукратного количества операций, которые были выполнены для инициализации перестройки таблицы, поэтому общие затраты остаются линейными. [1]

Линейное зондирование характеризуется выявлением одного из трех возможных исходов зондирования: если позиция таблицы содержит элемент, ключ которого совпадает с искомым, имеет место попадание при поиске; в противном случае ( если позиция таблицы содержит элемент, ключ которого не совпадает с искомым) мы просто зондируем позицию таблицы со следующим по величине индексом, продолжая этот процесс ( возвращаясь к началу таблицы при достижении ее конца) до тех пор, пока не будет найден искомый ключ или пустая позиция таблицы. Если содержащий искомый ключ элемент должен быть вставлен вслед за неудачным поиском, он помещается в пустую область таблицы, в которой поиск был завершен. Программа 14.4 - это реализация АТД таблицы символов, где используется этот метод. [2]

Сравнение линейного зондирования и двойного хеширования с раздельным связыванием выполнить сложнее, поскольку необходимо точно учитывать используемый объем памяти. Раздельное связывание использует дополнительный объем памяти для связей; методы с открытой адресацией используют дополнительную память неявно внутри таблицы для завершения последовательностей зондирования. Следующий конкретный пример иллюстрирует ситуацию. Предположим, что имеется таблица М списков, построенная при помощи раздельного связывания, что средняя длина списков равна 4, а каждый элемент и каждая связь занимают по одному машинному слову. Предположение, что элементы и ссылки занимают одинаковый объем памяти, оправдано во многих ситуациях, поскольку очень большие элементы будут заменены ссылками на них. В этом случае таблица занимает 9М слов в памяти ( 4Л / для элементов и 5М для связей), и для выполнения поиска в среднем требуется 2 зондирования. Но при линейном зондировании для 4Л / элементов в таблице размером 9 Л / требуется всего ( 1 1 / ( 1 - 4 / 9)) / 2 1.4 зондирований для обнаружения попадания при поиске - что на 30 процентов меньше, чем требуется для раздельного связывания при том же объеме используемой памяти; а при линейном зондировании для 4Л / элементов в таблице размером 6М требуется 2 зондирования для обнаружения попадания при поиске ( в среднем) и, следовательно, используется памяти на 33 процента меньше, чем при раздельном связывании при том же времени выполнения. [3]

При использовании линейного зондирования размер таблицы больше, чем при раздельном связывании, поэтому необходимо, чтобы M N, но общий используемый объем памяти может быть меньше, поскольку никаких связей не используется. [4]

Двойное хеширование аналогично линейному зондированию, за исключением того, что вторая хеш-функция используется для определения шага поиска, который будет использоваться после обнаружения каждого конфликта. Шаг поиска должен быть ненулевым, а размер таблицы и шаг поиска должны быть взаимно простыми числами. Функция remove для линейного зондирования ( см. программу 14.5) не работает с двойным хешированием, поскольку любой ключ может присутствовать во множестве различных последовательностей зондирования. [5]

Данные экспериментального исследования реализаций хеш-таблиц. [6]

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

Средние злтраты Ш1 ныполиение линейного зондирования зависят от способа объединения элсмснтпн н непрерывные крупны занятых ячеек тл & ллкы, Eiajhrii-ituuc xrwcmcpa. [8]

Простейший метод открытой адресации называется линейным зондированием ( linear probing): при наличии конфликта ( когда хеширование выполняется в место таблицы, которое уже занято элементом с ключом, не совпадающим с ключом поиска) мы просто проверяем следующую позицию в таблице. [9]

Исходя из самого способа образования таблицы, ключи в таблице, построенной линейным зондированием, размещаются в случайном порядке. Поэтому линейное зондирование не подходит для приложений, в которых эти операции выполняются часто. [10]

На этих диаграммах показано размещение записей при их вставке в хеш-таблицу с использованием линейного зондирования ( рисунок в центре) и двойного хеширования ( рисунок внизу), при распределении ключей, показанном на верхней диаграмме. [11]

Лемма 14.5 Сохраняя коэффициент загрузки меньшим, чем - f - Jt для линейного зондирования, и меньшим, чем 1 - 1 / 1 для двойного хеширования, можно обеспечить, чтобы в среднем для выполнения всех поисков требовалось менее t зондирований. [12]

Вопросы сравнения используемого объема памяти подробно рассматриваются в разделе 14.5. Пока же давайте проанализируем время выполнения линейного зондирования как функцию ос. [13]

Какое время может потребоваться в худшем случае для вставки N ключей в первоначально пустую таблицу при использовании линейного зондирования. [14]

К обсуждаемой группе задач тесно примыкает вопрос об оценке границ применимости по мощности уравнений оптической локации для традиционных схем линейного зондирования при использовании в последних ( с целью увеличения отношения сигнал / шум) лазерных источников с повышенной энергетикой. [15]

Страницы: 1 2 3 4