Книга: Фундаментальные алгоритмы и структуры данных в Delphi
Простая функция хеширования для строк
Простая функция хеширования для строк
Похоже, что приведенные в предыдущем разделе рассуждения наталкивают на мысль о необходимости использования весовых коэффициентов, соответствующих позиции каждого символа в строке во избежание конфликтов при использовании анаграмм в качестве ключей. Это приводит к следующей реализации (исходный код можно найти на 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-1.
- Инструмент командной строки gbak
- Инструмент командной строки gfix
- 2.1.3. Функция getopt_long()
- Как выделить строку, столбец и ячейки
- Удобная операция объединения строк
- Группировка по встроенным функциям и UDF
- Работа со строками
- Преобразование строки в целое: stoi( )
- 19.1.1. Функция jQuery()
- Функция strcmp( )
- Управление функциями узла
- Функция программного обеспечения