Структуры и алгоритмы обработки данных


Методы разрешения коллизий


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

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

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

Процедура удаления из таблицы сводится к поиску элемента и его удалению из цепочки переполнения.

pic3_2.gif (2799 bytes)

Рис.3.2. Разновидности методов разрешение коллизий

pic3_3.gif (1546 bytes)

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

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

pic3_4.gif (4468 bytes)

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

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

a=h(key) + c*i ,

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

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

a = h(key2) + c*i + d*i 2

Благодаря нелинейности такой адресации уменьшается число проб при большом числе ключей-синонимов.

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

Еще одна разновидность метода открытой адресации, которая называется двойным хешированием, основана на нелинейной адресации, достигаемой за счет суммирования значений основной и дополнительной хеш-функций




Начало  Назад  Вперед



Книжный магазин