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

Скачать книгу

только цифры и буквы английского алфавита, то минимальным значением хэш-функции будет сумма трех кодов цифры «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-H1 mod Н2, где Н1 и Н2 – простые числа, выбранные таким образом, чтобы H1 было в диапазоне от Н2/2 до Н2. Причем, чтобы этот генератор выдавал максимально длинную последовательность во всем диапазоне от HASH_MIN до HASH_MAX, Н2 должно быть максимально близко к величине HASH_MAX – HASН_МIN + 1. В данном случае диапазон содержит 223 элемента, и поскольку 223 – простое число, то возьмем Н2 = 223 (если бы размер диапазона не был простым числом, то в качестве Н2 нужно было бы взять ближайшее к нему меньшее простое число). В качестве H1 возьмем 127: H1 = 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)

Скачать книгу