Алексей Молчанов - Системное программное обеспечение. Лабораторный практикум

В качестве примера выполнения лабораторной работы возьмем сопоставление двух методов: хэш-адресации с рехэшированием на основе псевдослучайных чисел и комбинации хэш-адресации с бинарным деревом. Если обратиться к приведенной выше табл. 1.1, то такой вариант задания будет соответствовать комбинации методов 2 и 7 (в табл. 1.2 среди вариантов заданий такая комбинация отсутствует).

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

Будем считать, что прописные и строчные буквы в идентификаторах различны. [2]В качестве кодов символов возьмем коды таблицы ASCII, которая используется в вычислительных системах на базе ОС типа Microsoft Windows. Тогда, если положить, что строка из области определения хэш-функции содержит только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «0», а максимальным значением – сумма трех кодов литеры «z».

Таким образом, область значений выбранной хэш-функции в терминах языка Object Pascal может быть описана как:

(Ord(0 )+Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z')+Ord('z'))

Диапазон области значений составляет 223 элемента, что удовлетворяет требованиям задания (не менее 200 элементов). Длина входных идентификаторов в данном случае ничем не ограничена. Для удобства пользования опишем две константы, задающие границы области значений хэш-функции:

HASH_MIN = Ord(0 )+Ord(0 )+Ord(0 );

HASH_MAX = Ord('z')+Ord('z')+Ord('z').

Сама хэш-функция без учета рехэширования будет вычислять следующее выражение:

Ord(sName[1]) + Ord(sName[(Length(sName)+1) div 2]) + Ord(sName[Length(sName);

здесь sName – это входная строка (аргумент хэш-функции).

Для рехэширования возьмем простейший генератор последовательности псевдослучайных чисел, построенный на основе формулы F = i-H 1mod Н 2, где Н 1и Н 2– простые числа, выбранные таким образом, чтобы H 1было в диапазоне от Н 2/2 до Н 2. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от HASH_MIN до HASH_MAX, Н 2должно быть максимально близко к величине HASH_MAX – HASН_МIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 – простое число, то возьмем Н 2= 223 (если бы размер диапазона не был простым числом, то в качестве Н 2нужно было бы взять ближайшее к нему меньшее простое число). В качестве H 1возьмем 127: H 1= 127.

Опишем соответствующие константы:

REHASH1 = 127;

REHASH2 = 223;

Тогда хэш-функция с учетом рехэширования будет иметь следующий вид:

function VarHash(const sName: string; iNum: integer):longint;

begin

Result:=(Ord(sName[1])+Ord(sName[(Length(sName)+1) div 2])

+ Ord(sName[Length(sName)]) – HASH_MIN

+ iNum*REHASH1 mod REHASH2)

mod (HASH_MAX-HASH_MIN+1) + HASH_MIN;

if Result < HASH_MIN then Result:= HASH_MIN;

end;

Входные параметры этой функции: sName – имя хэшируемого идентификатора, iNum – индекс рехэшированиея (если iNum = 0, то рехэширование отсутствует). Строка проверки величины результата (Result < HASH_MIN) добавлена, чтобы исключить ошибки в тех случаях, когда на вход функции подается строка, содержащая символы вне диапазона 0 ..'z' (поскольку контроль входных идентификаторов отсутствует, это имеет смысл).

Для комбинации хэш-адресации и бинарного дерева можно использовать более простую хэш-функцию – сумму кодов первого и среднего символов входной строки. Диапазон значений такой хэш-функции в терминах языка Object Pascal будет выглядеть так:

(Ord(0 )+Ord(0 ))..(Ord('z')+Ord('z'))

Этот диапазон содержит менее 200 элементов, однако функция будет удовлетворять требованиям задания, так как в комбинации с бинарным деревом она будет обеспечивать обработку неограниченного количества идентификаторов (максимальное количество идентификаторов будет ограничено только объемом доступной оперативной памяти компьютера).

Без применения рехэширования эта хэш-функция будет выглядеть значительно проще, чем описанная выше хэш-функция с учетом рехэширования:

function VarHash(const sName: string): longint;

begin

Result:=(Ord(sName[1])+Ord(sName[(Length(sName)+1) div 2])

– HASH_MIN) mod (HASH_MAX-HASH_MIN+1) + HASH_MIN;

if Result < HASH_MIN then Result:= HASH_MIN;

end.

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

Структура данных таблицы идентификаторов (назовем ее TVarInfo) должна содержать в обязательном порядке поле имени идентификатора (поле sName: string), а также поля дополнительной информации об идентификаторе по усмотрению разработчиков компилятора. В лабораторной работе не предусмотрено хранение какой-либо дополнительной информации об идентификаторах, поэтому в качестве иллюстрации информационного поля включим в структуру TVarInfo дополнительную информационную структуру TAddVarInfo (поле pInfo: TAddVarInfo).

Поскольку в языке Object Pascal для полей и переменных, описанных как class, хранятся только ссылки на соответствующую структуру, такой подход не приведет к значительным расходам памяти, но позволит в будущем хранить любую информацию, связанную с идентификатором, в отдельной структуре данных (поскольку предполагается использовать создаваемые программные модули в последующих лабораторных работах). В данном случае другой подход невозможен, так как заранее не известно, какие данные необходимо будет хранить в таблицах идентификаторов. Но разработчик реального компилятора, как правило, знает, какую информацию требуется хранить, и может использовать другой подход – непосредственно включить все необходимые поля в структуру данных таблицы идентификаторов (в данном случае – в структуру TVarInfo) без использования промежуточных структур данных и ссылок.

Первый подход, реализованный в данном примере, обеспечивает более экономное использование оперативной памяти, но является более сложным и требует работы с динамическими структурами, второй подход более прост в реализации, но менее экономно использует память. Какой из двух подходов выбрать, решает разработчик компилятора в каждом конкретном случае (второй подход будет проиллюстрирован позже в примере к лабораторной работе № 4).