Точность этих выражений уменьшается с приближением значения а к 1, но в данном случае это не важно, поскольку в любом случае линейное зондирование не следует использовать в почти заполненной таблице. Для меньших значений а уравнения достаточно точны. Ниже приведена таблица обобщенных значений ожидаемого количества зондирований, требуемых для обнаружения попаданий и промахов при поиске с использованием линейного зондирования:

коэффициент загрузки (а)

1/2 2/3 3/4 9/10

попадание при поиске 1.5 2.0 3.0 5.5 промах при поиске 2.5 5.0 8.5 55.5

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

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

Исходя из самого способа образования таблицы, ключи в таблице, построенной линейным зондированием, размешаются в случайном порядке. В результате операции sort и select абстрактного типа данных требуют реализации с самого начала по одному из методов, описанных в главах 6-10. Поэтому линейное зондирование не подходит для приложений, в которых эти операции выполняются часто.

А как удалить ключ из таблицы, построенной с помощью линейного зондирования? Его нельзя просто удалить, поскольку элементы, которые были вставлены позже, могут вызывать пропуск этого элемента и поэтому поиск таких элементов мог бы постоянно прерываться на пустой позиции, оставленной удаленным элементом. Одно из решений этой проблемы заключается в повторном хешировании всех элементов, для которых эта проблема могла бы возникнуть - между удаленным элементом и следующей незанятой позицией справа от него. Пример, иллюстрирующий этой процесс, приведен на рис. 14.8. Программа 14.5 содержит реализацию этого подхода. В разреженной таблице в большинстве слу-

м S и р

о 3 4 в

G®m S и р

6 м S Н р

G S HP

G® S HP

и р ©hp

s р s® р

G м S н G m(p)s Н

а С е R i n

а С Е Я Г N

а С е R 1 n

а С е R I N

а С Е R i n

а с е R I N

а С е R i n

а С Е R IN

а С Е R I N

а С е R i n

01 23456789 10 11 12

РИСУНОК 14.8 УДАЛЕНИЕ В ХЕШ-ТАБЛИЦЕ, ИСПОЛЬЗУЮЩЕЙ ЛИНЕЙНОЕ ЗОНДИРОВАНИЕ

На этой диаграмме демонстрируется процесс удаления Хиз таблицы, показанной на рис. 14.7. Во второй строке показан результат простого удаления Xиз таблицы, что неприемлемо, поскольку М и Р отрезаются от своих хеш-позиций пустой позицией, оставленной ключом X. Поэтому ключи М, S, Ни Р (расположенные справа отХв этом же кластере) повторно вставляются в указанном порядке с использованием хеш-Значений, указанных вверху, и с разрешением конфликтов с помощью линейного зондирования. М заполняет свободное место, оставленное ключомX, затем Su Н вставляются в таблицу, не вызывая конфликтов, а затем Р вставляется в позицию 2.

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

Программа 14.5 Удаление из хеш-таблицы, использующей линейное зондирование

Для удаления элемента с заданным ключом мы выполняем его поиск и заменяем его элементом nullltem. Затем необходимо внести изменения на случай, если какой-либо элемент, расположенный справа от теперь незанятой позиции, помещается в эту поз1цию или левее нее, поскольку свободная позиция приводила бы к прерыванию поиска такого элемента. Поэтому выполняется повторная вставка всех элементов, которые располагаются в одном кластере с удаленным элементом и правее него. Поскольку таблица заполнена менее чем на половину, в среднем количество повторно вставляемых элементов будет мало.

void remove (Item х) { int i = hash (x.key О г М) , j ; while (!st[i] .nullO ) if (X.keyO == st[i].key()) break;

else i = (i+1) % M; if (st[i].null 0) return; st[i] = nullltem; N-;

for (j = i+1; !st[j] .nullO ; j = (j+1) % M, N-)

{ Item V = st[j]; st[j] = nullltem; insert (v) ; }

Упражнения

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

> 14,25 Приведите содержимое хеш-таблицы, образованной в результате вставки элементов с ключами EASYQUTIONb указанном порядке в первоначально пустую таблицу размером Л/= 16 при использовании линейного зондирования. Используйте хеш-функцию Ilk mod Мдля преобразования к-тоРу буквы алфавита в индекс таблицы.

14.26 Выполните упражнение 14.25 для Л/= 10.

о 14.27 Создайте программу, которая вставляет 10 случайных неотрицательных чисел, меньших чем 10, в таблицу размером 10, использующую линейное зондирование. Программа должна в графическом виде выводить количество зондирований, используемых для каждой из 10 последовательных вставок.

14.28 Создайте программу, которая вставляет 7V/2 случайных целых чисел в таблицу размером N, использующую линейное зондирование, а затем на основании длин кластеров вычисляет средние затраты на обнаружение промаха при поиске в результирующей таблице, для N = 10 10 *, 10 и 10.

14.29 Создайте программу, которая вставляет N/1 случайных целых чисел в таблицу размером N, использующую линейное зондирование, а затем вычисляет средние затраты на обнаружение попадания при поиске в результирующей Ta6jnme, для Л = 10 , 10*, 10 и 10. В конце не выполняйте поиск всех ключей (отслеживайте затраты на построение таблицы).

14.30 Определите экспериментальным путем, изменяются ли средние затраты на обнаружение попаданий и промахов при поиске в случае выполнения длинной последовательности чередующихся случайных вставок и удалений с помощью программ 14.4 и 14.5 в хещ-таблице размером 2N, содержащей Л ключей, для Л = 10, 100 и 1000 и до Л пар удалений-вставок для каждого значения n.

14.4 Двойное хеширование

Основной принцип линейного зондирования (а, в действительности, и любого метода хеширования) - обеспечение гарантии того, что при поиске конкретного ключа выполняется поиск каждого ключа, который отображается тем же адресом в таблице (в частности, самого ключа, если он присутствует в таблице). Однако, как правило, при использовании схемы с открытой адресацией другие ключи также исследуются, особенно, когда таблица начинает приближаться к заполненному состоянию. В примере, приведенном на рис. 14.7, поиск ключа N сопряжен с просмотром ключей С, Е, R и I, ни один из которых не имеет такого же хеш-значения. Хуже того, вставка ключа с одним хеш-значением может существенно увеличить время поиска ключей с другими хеш-значениями: на рис. 14.7 вставка ключа М приводит к увеличению времени поиска для позиций 1 - 12 и 0-1. Это явление называется кластеризацией, поскольку оно связано с процессом образования кластеров. Оно может значительно замедлять линейное зондирование для почти заполненных таблиц.

К счастью, существует простой способ избежать возникновения проблемы кластеризации - двойное хеширование. Основная стратегия остается той же, что и при выполнении линейного зондирования. Единственное различие состоит в том, что вместо исследования кащюй позиции таблицы, следующей за конфликтной, мы используем вторую хеш-функцию для получения постоянного шага, который будет использоваться для последовательности зондирования. Реализация метода приведена в профамме 14.6.

Программа 14.6 Двойное хеширование

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

void insert(Item item) { Key V = item, key 0 ; int i = hash(v, M) , к = hashtwo(v, M) ; while (!st[i] .nullO) i = (i+k) % M; st[i] = item; N++;

Item search(Key v) { int i = hash(v, M) , к = hashtwo(v, M) ; while (!st[i] .nullO ) if (V = st[i].key()) return st[i];

else i = (i+k) % M; return nullltem;