Простая функция хеширования для строк

Простая функция хеширования для строк

Похоже, что приведенные в предыдущем разделе рассуждения наталкивают на мысль о необходимости использования весовых коэффициентов, соответствующих позиции каждого символа в строке во избежание конфликтов при использовании анаграмм в качестве ключей. Это приводит к следующей реализации (исходный код можно найти на 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.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Шаг первый: простая страница

Из книги автора

Шаг первый: простая страница Вначале бралась обычная страница, для которой использовалось только gzip-сжатие HTML-файла. Это самое простое, что может быть сделано для ускорения загрузки страницы. Данная оптимизация бралась за основу, с которой сравнивалось все остальное. Для


Простая железнодорожная система

Из книги автора

Простая железнодорожная система Вы легко построите железнодорожную систему, состоящую из одного пути с остановками и двумя простыми конечными точками. Обеспечьте энергией начало железной дороги, выкопав яму 2?1 и поместив в нее энергорельсы. Последний блок рельсов


Более простая версия функции str_cli

Из книги автора

Более простая версия функции str_cli Неблокируемая версия функции str_cli, которую мы только что показали, нетривиальна: около 135 строк кода по сравнению с 40 строками версии, использующей функцию select с блокируемым вводом-выводом (см. листинг 6.2), и 20 строками начальной версии,


Пример: простая программа с уведомлением

Из книги автора

Пример: простая программа с уведомлением Прежде чем углубляться в тонкости сигналов реального времени и потоков Posix, мы напишем простейшую программу, включающую отправку сигнала SI6USR1 при помещении сообщения в пустую очередь. Эта программа приведена в листинге 5.8, и мы


Глава 4 Простая

Из книги автора

Глава 4 Простая В этой главе рассматриваются модификаторы и составные объекты. Действие модификаторов направлено на изменение формы объекта, взаимодействие двух объектов приводит к созданию третьего – составного. Моделирование с использованием модификаторов и


9.2. Простая ассемблерная вставка

Из книги автора

9.2. Простая ассемблерная вставка Вот как с помощью функции asm() осуществляется сдвиг числа на 8 битов вправо:asm("shrl $8, %0" : "=r" (answer) : "r" (operand) : "cc");Выражение в скобках состоит из секций, разделенных двоеточиями. В первой секции указана ассемблерная инструкция и ее операнды.


Функции хеширования

Из книги автора

Функции хеширования Алгоритм, который необходимо рассмотреть в первую очередь, - функция хеширования. Это подпрограмма, которая будет принимать ключ элемента и магическим образом преобразовывать его в значение индекса. Очевидно, что если в хеш-таблице предусмотрено


Функции хеширования PJW

Из книги автора

Функции хеширования PJW В разделе, посвященном хеш-таблицам, книги "Compilers: Principles, Techniques, and Tools" ("Компиляторы: принципы, технологии, инструменты"), Ахо (Aho) и других, которая была издана Addison-Wesley [2], описана функция хеширования, созданная П. Дж. Вайнбергером (P. J. Weinberger). Эту


Первая простая реализация

Из книги автора

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


Вторая простая реализация

Из книги автора

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


Простая реализация подсказок с помощью MFC

Из книги автора

Простая реализация подсказок с помощью MFC Microsoft упростила добавление подсказок к кнопкам на панелях инструментов. Если вы используете AppWizard, этот процесс происходит автоматически. При генерации вашего приложения с помощью AppWizard щелкните флажок "Docking toolbar". После генерации


Пример 22-1. Простая функция

Из книги автора

Пример 22-1. Простая функция #!/bin/bashfunky (){ echo "Это обычная функция."} # Функция должна быть объявлена раньше, чем ее можно будет использовать. # Вызов функции.funkyexit 0Функция должна быть объявлена раньше, чем ее можно будет использовать. К сожалению, в Bash нет возможности


Простая архитектура PKI

Из книги автора

Простая архитектура PKI Архитектура PKI может быть очень простой, если у пользователей - простые требования. В этом разделе рассматриваются два типа простой архитектуры: одиночный УЦ и списки доверия УЦ. Простая архитектура достаточна для связывания пользователей одного и