Похоже, что приведенные в предыдущем разделе рассуждения наталкивают на мысль о необходимости использования весовых коэффициентов, соответствующих позиции каждого символа в строке во избежание конфликтов при использовании анаграмм в качестве ключей. Это приводит к следующей реализации (исходный код можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshBse.pas).

Листинг 7.1. Простая функция хеширования строковых ключей

function TDSimpleHash( const aKey : string;
aTableSize : integer) : integer;
var
i : integer;
Hash : longint;
begin
Hash := 0;
for i : = 1 to length (aKey) do
Hash := ((Hash * 17) + ord(aKey[i])) mod aTableSize;
Result := Hash;
if (Result < 0) then
inc(Result, aTableSize);
end;

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

Эта подпрограмма достаточно удачна. В ней для каждого символа выполняется всего несколько арифметических операций - к сожалению, в их числе и операция деления - и поэтому она достаточно эффективна. В реальных ситуациях строковые ключи оказываются в значительной степени подобными друг другу (вспомните, например, названия классических музыкальных произведений), а подпрограмма из похожих входных значений создает хеш-значения, которые выглядят случайными. Заключительный оператор If требуется потому, что промежуточное значение переменной Hash может быть отрицательным (такова неприятная "особенность" операции деления по модулю Delphi), а программа*, вызывающая эту подпрограмму, будет ожидать результат, значение которого лежит в диапазоне от 0 до TableSize-l.

Функции хеширования || Оглавление || Функции хеширования PJW


Фундаментальные алгоритмы и структуры данных в Delphi



Новости за месяц

  • Август
    2019
  • Пн
  • Вт
  • Ср
  • Чт
  • Пт
  • Сб
  • Вс