Методы сортировки и поиска

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


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


Рис. 4.18.

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


Рис. 4.19.

Рис. 4.20.

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

Содержание раздела