Фамилия (ключ) Числовое значение ключа

Скворцов 81257352

Соколов 8515252

Строков 8975152

Супруненко 8067045415

2. приведение ключа к требуемому порядку:

· метод квадратов. Преобразование ключа показано в таблице 15:

Таблица 15

Числовое значение ключа	Квадрат значения	Средняя часть числа (результат)
	6602757254051900
	72509516623504
	80553353423104
	65077221727672500000

· сдвиг разрядов. Преобразование ключа показано таблице 16:

Таблица 16

Числовое значение ключа	Совмещенные разряды	Результат сложения	Результат
старшие разряды	младшие разряды
			(15)477
			(13)762
			(13)(10)(12)2
			(12)5(10)85

Поскольку для последнего ключа (выделен полужирным курсивом) результат имеет 5 разрядов (требуется 4), с этим значением ключа продолжается работа по тому же методу (таблица 17):

Таблица 17

Числовое значение ключа	Совмещенные разряды	Результат сложения	Результат
старшие разряды	младшие разряды

· метод складывания. Преобразование ключа показано таблицей 18:

Таблица 18

Числовое значение ключа	Наложенные части числа	Результат сложения	Результат
левая часть	средняя часть	правая часть
				3(13)98
			8 25	(13)177
			8 25	(17)776
				(13)5(13)9

3) формирование реальных номеров бакетов. Для определения константы С выполним следующие вычисления:

С = N_max/9999 = 0009/9999 = 0,0009.

Тогда номера бакетов рассчитаны по приведенной ранее формуле и представлены в таблице 19:

Таблица 19

Фамилия (ключ)	Номер бакета
метод квадратов	сдвиг разрядов	метод складывания
Скворцов
Соколов
Строков
Супруненко

Для анализа эффективности методов построим схему распределения элементов исходного линейного списка (таблица 11) по бакетам:

1. метод квадратов. Распределение элементов по бакетам показано в таблице 20:

Таблица 20

Номер бакета	Содержимое бакета
	Строков	Иван	Иванович		ул. Красная, 9 - 2
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3
Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5

2. сдвиг разрядов. Распределение элементов по бакетам показано в таблице 21:

Таблица 21

Номер бакета	Содержимое бакета
	Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
Строков	Иван	Иванович		ул. Красная, 9 - 2
	Скворцов	Олег	Иванович		пр. Мира, 45 - 3

3. метод складывания. Распределение элементов по бакетам показано в таблице 22:

Таблица 22

Номер бакета	Содержимое бакета
	Скворцов	Олег	иванович		пр. Мира, 45 - 3
	Соколов	Юрий	Кузьмич		ул. Леонова, 23 - 98
Супруненко	Виктор	Егорович		Каштановая аллея, 23 - 5
	Строков	Иван	Иванович		ул. Красная, 9 - 2

Как показывает анализ, все три метода с одинаковой равномерностью заполняют бакеты: один бакет содержит два элемента, остальные – по одному, т.е. методы равноэффективны.

Решим задачу просмотра элемента.

Пример 10. По ключу Супруненко требуется просмотреть домашний адрес студента, т.е. q^{просмотр} = (Фамилия = Супруненко, Домашний адрес), где К_доступ = Супруненко. Пусть линейный список после размещения соответствует таблице 22. Задача решается следующим образом:

1. по приведенным выше алгоритмам рандомизации определяется номер бакета для нужного ключа доступа – это 0004;

2. в данном бакете находится линейный список элементов, в общем случае, не упорядоченный по ключу. Поэтому к нему применим метод последовательного сканирования. Анализируется первый элемент бакета с ключом Соколов: Соколов = Супруненко;

3. поскольку условие не выполняется, выбирается следующий элемент;

4. его ключевое поле сравнивается с ключом доступа: Супруненко = Супруненко; условие выполняется, поэтому выводится результат – Каштановая аллея, 23 – 5. Алгоритм заканчивает работу.