Закрытое хеширование

При закрытом хешировании в таблице сегментов хранятся непосредственно элементы словаря, а не заголовки списков. Поэтому в каждом сегменте может храниться только один элемент словаря. При закрытом хешировании применяется методика повторного хеширования. Если произойдет попытка поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное. Если свободных сегментов нет, то таблица заполнена, и элемент х вставить в нее нельзя.

Рассмотрим пример заполнения хеш-таблицы в случае закрытого хеширования (рис. 4).

Рис. 4 – Частично заполненная хеш-таблица

Здесь В=8 и ключи a, b, c, d имеют хеш-значения h(a)=3, h(b)=0, h(c)=4, h(d)=3. Для добавления в таблицу элемента d применим методику линейного хеширования, когда Тогда, если сегмент 3 уже занят, то проверяются на занятость сегменты 4, 5, 6, 7, 0, 1, 2 (именно в таком порядке). 5-ый сегмент оказался первым пустым сегментом, поэтому элемент d был вставлен в него

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

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

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

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

Рис. 5 – Разрешение коллизий при добавлении элементов

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

Линейное опробование сводится к последовательному перебору элементов таблицы с некоторым фиксированным шагом

a=h(key) + c* i,

где i – номер попытки разрешить коллизию. При шаге равном единице происходит последовательный перебор всех элементов после текущего.

Квадратичное опробование отличается от линейного тем, что шаг перебора элементов нелинейно зависит от номера попытки найти свободный элемент

a = h(key2) + c* i + d* i ² .

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

Рис. 6 – Разрешение коллизий при добавлении элементов методами

открытой адресации

Алгоритмы работы с хеш-таблицами методами открытой адресации

Опишем алгоритмы вставки и поиска элементов для метода линейного опробования.

Вставка

i = 0

a = h(key) + i*c

Если t(a) = свободно, то t(a) = key, записать элемент, стоп элемент добавлен

Лекция 3

План лекции:

1. Полустатические и динамические структуры данных.

2. Абстрактный тип данных «список».

3. Сравнение различных реализаций списков.

4. Дважды связные списки.

Не нашли, что искали? Воспользуйтесь поиском: