Разрешение коллизий методом цепочек.

Мы уже говорили, что некотор хеш-адреса могут быть одинаковыми для различных ключей. Вероятно, самый очевидный путь решения этой проблемы — поддержка М связных списков, по одному для каждого возможного значения хеш-кода. Поле LINK должно быть включенс каждую запись; кроме того, следует иметь М головных узлов списков, перенумерованных, скажем, от 1 до М. После хеширования ключа мы просто выполня последовательный поиск в списке номер f {p) + 1

На рис. 38 показанапростая схема с цепочками при М = 9 для последовательностииз ключей

К = EN,TO, TRE, FIRE, FEM, SEKS,SYV (11)

(представляющих числа от 1 до 7 на норвежском языке), имеющих хеш-коды

f(p)+1=3, 1. 4,1, 5, 9, 2 (12)

соответственно. В первом списке содержится два элемента, три списка пусты.

В связи с тем, что цепочки коротки, рассматриваемый здесь метод являет весьма быстродействующим. Если 365 человек соберутся вместе в одной комнате, вероятно, окажется много пар, имеющих один и тот же день рождения, однако среднее количество людей с данным днем рождения равно только 1! В общ случае, если имеется N ключей и М списков, средний размер списка будет равN/M; значит, хеширование приводит к уменьшению среднего количества обращений по сравнению с последовательнымпоиском, примернов М раз

Индексы

Для ускорения поиска записей в массиве используется дополнительная информация, организованная в виде массива индексов.

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

Имеются три важные разновидности индексов:

· информация о каждой записи основного массива попадает в индекс (сплошная индексация);

· номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d > 1. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным;

· ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию.

Сплошной индекс связан с созданием инвертированного массива ключевых атрибутов к основному массиву. Этот случай рассмотрен в теме ИПС, инвертированные файлы.

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

В индекс выносится информация о записях, номера которых образуют арифметическую прогрессию с шагом d. На рис. 6.5 показаны ключевые атрибуты основного массива и состояние массива индексов для d=3

 

Рис. 6.5. Индексно-последовательная организация данных

Поиск значения q в индексно-последовательном массиве происходит в две стадии:

· в массиве индексов (который отсортирован в силу упо­рядоченности основного массива);

· среди записей основного массива, расположенных между двумя соседними индексами, найденными на первой стадии.

Применение индексов приводит к ускорению доступа, если основной массив располагается на внешнем запоминающем устройстве, а массив индекса может быть полностью разме­щен в оперативной памяти ЭВМ.

Если ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию, мы получаем ситуацию с адресной функцией для индекса (ран­домизация индекса).

Точное описание рандомизированного индекса состоит в следующем. Индекс с номером n хранит адрес записи основ­ного массива, ключ которой равен или непосредственно боль­ше значения

p (1)+z (n-1),

где z - константа (шаг арифметической прогрессии);

р (1) - значение ключа первой записи основного массива.

На рис. 6.4 показаны ключевые атрибуты основного массива (идентичные с предыдущим примером) и состояние мас­сива рандомизированных индексов для z = 10. Примечательно, что значения ключей в таком индексе хранить не нужно.

Рассмотрим поиск с использованием рандомизированных ин­дексов. На первой стадии номер требуемого далее индекса опреде­ляется по формуле

Результат деления округляется в меньшую сторону.Интервалзаписей основного массива на второй стадии поискаопределяетсяадресами, указанными в n-м и (n+1)-м индексах.

 

Рис. 6.4. Рандомизация индекса

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

Среди ключевых атрибутов записи устанавливается поря­док старшинства. Извлекаемые на обработку записи должны быть упорядочены в пределах всего массива по самому стар­шему ключу. В пределах группы записей с одинаковым значе­нием старшего ключа должна соблюдаться упорядоченность по значениям следующего по старшинству ключа и т. д. Про­ще всего представить упорядоченность по нескольким клю­чам с помощью следующей схемы.

Пример

Рассмотрим записи с четырьмя атрибутами в порядке старшин­ства слева направо А 1, А2, АЗ, А4. Значения А1 упорядочены (для примера) по возрастанию. На каждом множестве записей, кото­рые соответствуют одинаковому значению А1, реализована упо­рядоченность по возрастанию значений А2 для записей, у кото­рых значение А1 одинаково. Далее, на каждом множестве записей с одинаковыми парами значений атрибутов А1 и А2 соблюдается

упорядоченность значений по атрибуту АЗ. И, наконец, на каж­дом множестве записей с одинаковыми значениями атрибутов А1, А2, АЗ должна соблюдаться упорядоченность по возрастанию для атрибута А4.

Последовательный массив с такой упорядоченностью может обеспечивать быстрый доступ к данным по следующим сочетани­ям ключевых атрибутов а1+а2+а3+а4, а1+а2+а3, а1+а2 и а1.

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

Рассмотрим возможности создания нескольких массивов индексов в этой ситуации. Индекс удобно формировать не для одного ключевого атрибута, а для набора атрибутов. Естественно, что индекс ключевых атрибутов а1+а2+а3+а4 может также использоваться для быстрого доступа по ат­рибутам а1+а2+а3, а1+а2 и а1. Поэтому в нашем примере максимально необходимо создание 4 индексов с упорядо­ченностью атрибутов а1+а2+а3+а4, а1+а2+а4, а1+а3+а4,

а2+а3+а4.

Для доступа к данным по нескольким ключевым атрибу­там используется также мультисписковая организация данных. Мультисписком называется множество списков, организован­ных на общем множестве записей. Если требуется доступ к за­писям по I ключам, то формируется I списков для каждого клю­чевого атрибута в отдельности.

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

Пример

В табл. 3.2 показаны 14 записей с ключевыми атрибутами Фа­милия и Профессия (остальные атрибуты в данном случае несуще­ственны). На пересечении строки с некоторой фамилией и столбца с некоторой профессией указан номер записи, которая содержит именно эти значения в качестве ключей.

В простейшем случае мультисписок будет содержать два спис­ка - с указателем Фамилия - (А(1), А(2), А(3),..., А(13), А(14)) и суказателем Профессия- (А(3), А(6), А(12), А(1), А(7), А(10), А(13), А(2), А(4), А(8), А(14), А(5), А(9), А(11)).

Таблица 3.2. Мультисписок для двух клю-опы» ато-в-"—

Фамилия		Профессия
	слесарь	токарь	штамповщик	электрик
Бардин Басов Батов	А(3) А(6)	А(1)   А(7)	А(2) А(4)	А(5)
Белов			А(8)	А(9)
Иванов Исаев	А(12)	А(10) А(13)	А(14)	А(11)

 

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

Эффективная организация мультисписка предполагает выполнение следующих условий:

• число записей в каждом списке должно быть небольшим,

• адреса хранения записей должны монотонно возрастать. Для сокращения длины списков в мультисписке необходи­мо детализировать содержимое указателей. Например, указа-гель Фамилия = "Ба" определяет список (А(1), А(2), А(3), А(4), А(5), А(6), А(7)), указатель Фамилия = "Бе" - список (А(8), А(9)), указатель Фамилия = "И" - список (А(10), А(11), А(12), А(13), А(14)). Поскольку атрибут Профессия содержит четыре значения, возможно существование следующих четырех

списков: (А(3),А(6),А(12)); (А(1),А(7),А(10),А(13)); (А(2),А(4),А(8),А(14)); (А(5),А(9),А(11)).

При поиске в сокращенных списках необходимо сначала проанализировать все указатели, чтобы выбрать одну строку, заведомо содержащую требуемую информацию.

Рассмотрим запрос с условием

Фамилия ="Иванов" и Профессия = "электрик"

Потребуются три обращения к памяти для выбора списка (А(10), А,(11), А(12)),А(13), А(14)) и четыре обращения для выбора списка (А(5),А(9), А(11)). В указателях хранится длина каждого списка. Вторая строка короче, поэтому она просматривается полностью до извлечения нужной записи А(11).