Реферат: Хеш-функции
Рис. Раздельные цепочки.
ключа мы просто выполняем последовательный поиск в списке с
номером h(K)+1.
Рисунок иллюстрирует этот простой метод цепочек при M=9 для
последовательности семи ключей
K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|
(так называются числа от 1 до 7 по-норвежски), имеющих соответственные хеш-коды
h(K)+1 = 3, 1, 4, 1, 5, 9, 2.
Первый список содержит два элемента, три списка пусты.
Метод цепочек является весьма быстрым, поскольку списки коротки. Если в одной комнате собрать 365 человек, то найдется много пар, имеющих один и тот же день рождения, но данный день рождения в среднем имеет лишь один человек! Вообще, если имеется N ключей и M списков, средний размер списка равен N/M; таким образом, хеширование уменьшает количество работы, требуемое на последовательный поиск, примерно в M раз.
В целях экономии времени желательны большие M , но в этом случае многие ссылки будут пустыми, так что большая часть пространства, отводимого под M головных узлов, потратится зря. Для небольших по размеру записей напрашивается другой подход: можно наложить пространство для записей на пространство для головных узлов, отводя в таблице место под M записей и M ссылок, а не под N записей и M+N ссылок.
Иногда можно совершить один проход по данным и выяснить, какие головные узлы будут использоваться, вставляя на следующем проходе "переполняющие" записи в свободные щели. Часто, однако, это нежелательно или невозможно; нам хотелось бы иметь метод, при котором каждая запись обрабатывается лишь один раз, при первом поступлении в систему. Следующий алгоритм, принадлежащий Ф.Уильямсу, является общепринятым способом решения этой задачи.
alg C. (Поиск с вставкой по рассеянной таблице с цепочками.) Предлагаемый
алгоритм позволяет отыскать в таблице из M элементов данный ключ K.
Если K нет в таблице и она не полна, K вставляется в нее.
Элементы таблицы обозначаются через TABLE[i], 0≤i≤ M, и могут
быть двух различных типов: свободный и занятый. Занятый узел
содержит ключевое поле KEY[i], поле ссылки LINK[i] и, возможно,
другие поля.
Алгоритм использует хеш-функцию h(K). Для облегчения поиска свободного пространства используется вспомогательная переменная R; если таблица пуста, R=M+1; по мере проведения вставок будет оставаться в силе утверждение, что узлы TABLE|[j] заняты для всех j в диапазоне R≤j≤M.
Условимся, что узел TABLE[0] всегда будет свободен.
C1 .[Хеширование.] Установить i←h(K)+1. (Теперь 1≤i≤M.)
C2 .[Список?] Если узел TABLE[i] свободен, то перейти на C6.
(В противном случае этот узел занят, и мы последуем на имеющийся здесь
список занятых узлов).
C3 .[Сравнение.] Если K=KEY[i], поиск завершен удачно.
C4 .[Переход к следующему.] Если LINK[i]≠0, установить i←LINK[i] и вернуться на
C3.
C5 .[Найти свободный узел.] (Поиск был неудачным, и мы хотим найти в