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

Содержание 65
ОСНОВЫ АЛГОРИТМОВ И СТРУКТУР ДАННЫХ
При включении новый ключ можно писать как в пустые ячейки, так и в
ячейки, помеченные “удалено”.
Линейная расстановка интересна тогда, когда в таблице коэффициент
заполнения
%75
ячеек число
имён число
α ≤ = =
m
n
.
Посмотрим, что происходит на примере животных: (h(x ) – сумма
порядковых номеров букв, m=20).
Включение имён БЕГЕМОТ, ГАВИАЛ, ВАРАН, ЖИРАФ, ЗЕБРА,
КЕНГУРУ происходит без коллизий.
Произвёдём включение имени ПИТОН (h=15).
БЕГЕМОТ
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
ГАВИАЛ КЕНГУРУЗЕБРАЖИРАФВАРАНПИТОН
Z=ПИТОН
*
*
Рис. 63. Включение нового имени в таблицу
Таким образом, для включения z = ПИТОН потребовалось три сравнения.
Заметим, что новые имена с h(z) = 14,15,16,17,18 теперь будут включаться
на одно и то же место (ячейка 18). Таким образом, включение нового имени с
h(z) = 14 потребует пяти сравнений. Этот эффект называется вторичным
скучиваньем. Первичное скучиванье возникает, когда в таблицу вносят имена с
одинаковым значением хэш-функции. Вторичные скучивания – это следствие
того, что имена с различными значениями хэш-функции порождают
пересекающиеся последовательности адресов.
Таким образом, главным недостатком методов с линейной вторичной
расстановкой является тенденция к созданию смежных пакетов имён и слияние
этих пакетов в ходе последовательных включений в ещё более крупные пакеты.
При этом, при включении, в среднем будет просматриваться полпакета
ключей. Чем больше пакет, тем больше он тормозит работу и тем быстрее он
растет.
Чтобы избежать образования пакетов, достаточно при разрешении
коллизий взять шаг больше 1, причем для разных х надо взять разный шаг.
Часто используют следующую формулу:
)(
1 z A A i i i ∆+ =
− ,