Стр. 70 - Основы алгоритмов и структур данных

68 Содержание
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
4.9.4. Увеличение скорости разрешения коллизий
В любом из рассмотренных методов разрешения коллизий фактически
осуществляется последовательный перебор всех участвующих в коллизии
ключей. Следовательно, как и в методе последовательного поиска, можно
улучшить быстродействие при неуспешном поиске. Этого можно добиться,
если упорядочить цепочки имён, участвующих в коллизии.
Тогда алгоритму поиска можно останавливаться сразу, как только будет
обнаружен ключ, равный или больший чем исходный. Модификация алгоритма
включения более сложна, так как, часть элементов, участвующих в коллизии,
должна быть смещена на следующий адрес.
Алгоритм включения:
A = h0(z)mod m;
Δ = h0 (z)mod (m-2);
for (i=0 ;i < m; i++)
{
if M(A) ≥ z then
{
Y=M(A);
M(A) = z;
if (Y == λ) <выход>
z=Y;
A=(A+ Δ)mod m;
}
}
<неуспех: в таблице не хватило места, возможно z включено, но
исключено другое имя Y>
Алгоритм поиска / исключения написать самостоятельно!
Для поиска в такой таблице при α=0.95 число операций при неуспехе равно
примерно 3. При успешном поиске быстродействие не улучшилось.
Очевидное улучшение алгоритмов, основанных на упорядочивании
ключей, входящих в коллизию, состоит в том, чтобы внутри коллизирующего
списка вести не последовательный поиск, а, например, логарифмический или
организовать вторичное хеширование.