Алгоритм хеширования выполняется в три этапа:

1) первый этап выполняется только для нечисловых значений ключей и заключается в замене их числовыми значениями. Для этого составляется таблица соответствия символов алфавита, в котором записываются значения ключей, с цифрами от 1 до 9. Затем каждый символ нечислового значения ключа заменяется своим цифровым эквивалентом. Например, если нечисловые значения ключей определены на русском алфавите, такая таблица будет иметь вид:

а 1 и 9 р 8 ш 7

б 2 й 1 с 9 щ 8

в 3 к 2 т 1 э 9

г 4 л 3 у 2 ю 1

д 5 м 4 ф 3 я 2

е 6 н 5 х 4 ь 3

ж 7 о 6 ц 5 ъ 4

з 8 п 7 ч 6 ы 5

Очевидно, разным символам присваивается один цифровой код, что ведет к потере информации.

Тогда, например, для ключа со значением КОМПЬЮТЕР цифровой эквивалент имеет вид 264731168.

2) формируется относительный адрес элемента списка. Для этого числовое значение адреса приводится к порядку, равному порядку адресов памяти, где размещен список. Например, список размещен на диске в кластерах с номерами от 10 до 999, т.е. в адресах с порядком, равным 3. Тогда для ключа, полученного на предыдущем этапе, надо выполнить такое преобразование, чтобы из девятизначного числа превратить его в трехзначное. Подобные преобразования выполняются разными способами. Рассмотрим некоторые из них:

- возведение в квадрат. Числовое значение ключа возводится в квадрат и в полученном числе по центру выбирается нужное количество цифр. Для нашего случая 2647311682 = 70082591310644200, центральными цифрами являются 131. Таким образом, относительный адрес для ключа КОМПЬЮТЕР равен 131,

- метод складывания (не путать со сложением). Числовое значение ключа делится на три части: средняя часть (размещается по центру) имеет количество цифр, равное порядку адресов памяти, где размещен список; оставшиеся правая и левая части «заворачиваются» к средней и совпавшие цифры складываются до образования цифр. Например, для ключа 264731168 этот способ дает следующий результат:

264 731 168

левая средняя правая

часть часть часть

После складывания:

731- средняя часть

462 - левая часть, «завернутая» по месту стыка со средней частью

861 - правая «завернутая» часть.

После сложения совпавших цифр (сложение идет до достижения значения цифры): (7+4+8)(3+6+6)(1+2+1) = (19)(15)(4) = (1+9)(1+5)(4) = (10)(6)(4) = (1+0)(6)(4) = 164

Таким образом, относительный адрес для ключа КОМПЬЮТЕР, полученный вторым способом, равен 164,

- метод деления. Числовое значение ключа делится на количество адресов памяти, в которой размещается список. Остаток от деления – относительный адрес. Например, для ключа 264731168 и для числа адресов 989 (999 – 10) остаток от деления равен 593. Это и есть относительный адрес для ключа КОМПЬЮТЕР,

- метод сдвига. Числовое значение ключа делится на две равные части, которые смещаются друг навстречу другу так, чтобы общее число разрядов стало равно порядку адресов памяти. Совпавшие разряды складываются. Например, для ключа 264731168 и для тех же адресов:

02647[1] 31168

левая правая

часть часть

направление движения

правой и левой частей числа

02647 после сдвига

31168

3 3 7 (10)(15) = 337(1+0)(1+5)=33716

Поскольку полученное число имеет порядок, больший трех, процедура сдвига повторяется:

033 716

левая часть правая часть

033 после сдвига

716

749 – конечный результат – относительный адрес для ключа КОМПЬЮТЕР.

Очевидно, и этот этап дает потерю информации.

3) вычисление абсолютного адреса. Исходная информация – диапазон изменения относительных адресов (очевидно, от 0 до 999) и адреса размещения элементов списка в памяти (напомним, что список занимает кластеры с адресами от 10 до 999). Тогда абсолютный адрес для элементов списка получается по формуле:

<начальный адрес размещения списка> + <относительный адрес элемента> * const,

где const – константа, получаемая по формуле:

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

Для нашего случая const = 989 / 999 = 0,989

Тогда, например, для относительного адреса 199 абсолютный адрес (читай – номер кластера) равен 10 + 199*0,989 = 10+197 = 207.

2. Задания

1. Создать на диске линейный список в соответствии с вариантом (состав полей элементов списка выбрать самостоятельно по смыслу задачи).

2. Разработать алгоритмы и программы поиска нужной ин­формации в линейном списке в соответствии с вариан­том.

3. Выполнить автоматизированный сравнительный анализ методов адресации, данных в варианте, на основе обобщенного критерия - произведения числа обращений к машинному носителю на объем ин­формационной базы (вместе с индексами).

Варианты заданий

Таблица 1