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

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

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

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

Но все приведенные рассуждения являются чисто теоретическими. Чтобы получить представление о том, что хорошо, а что плохо, рассмотрим ряд функций хеширования.

Простейший случай - использование целочисленный ключей, когда элемент уникально идентифицируется целочисленным значением. Простейшей функцией хеширования, которую можно было бы использовать в этом случае, является операция деления по модулю. Если хеш-таблица содержит n элементов, хеш-значение ключа k вычисляется путем вычисления k по модулю n (если результат этой операции оказывается отрицательным, нужно просто добавить к нему n). Например, если n равно 16, то ключу 6 будет соответствовать индекс 6, ключу 44 - индекс 12 и т.д. В случае равномерного распределения значений ключей эта функция вполне подходила бы для работы, но в общем случае множество значений ключей не столь равномерно распределенное, и поэтому в качестве размера хеш-таблицы необходимо использовать простое число.

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

Для строковых ключей следует использовать метод, заключающийся в преобразовании строки в целочисленное значение с последующим применением операции деления по модулю для получения значения индекса, лежащего в диапазоне от 0 до n - 1.

Так как же преобразовать строку в целочисленное значение? Один из возможных способов предполагает использование длины строкового ключа. Преимущество применения этого метода состоит в простоте и высокой скорости выполнения. Однако его недостатком является генерирование множества конфликтов. На практике таких конфликтов возникает слишком много. Например, предположим, что нужно создать хеш-таблицу, которая должна содержать названия альбомов коллекции компакт-дисков. В частности, в принадлежащей автору коллекции компакт-дисков, насчитывающей несколько сот наименований, названия подавляющего большинства альбомов содержат от 2 до 20 символов. Использование длины названия альбома привело бы к возникновению множества конфликтов: альбом Bilingual в исполнении Pet Shop Boys конфликтовал бы с Technique в исполнении New Order и с Mind Bomb в исполнении The The. Таким образом, подобная функция хеширования совершенно неприемлема.

Более подходящей функцией хеширования было бы преобразование первых двух символов ключа в значение типа word. Затем для создания индекса можно было бы выполнить деление по модулю этого значения на длину хеш-таблицы. Такой подход вполне приемлем применительно к коллекции компакт-дисков рок- или поп-произведений, но не особенно подходит для коллекции компакт-дисков с классическими произведениями: все симфонии Бетховена преобразовывались бы в одно и то же хеш-значение, которое совпадало бы со значением для всех симфоний Рахманинова и для большинства симфоний Вогана-Вильямса.

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

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

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

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

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

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

Функции

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

Функции Существует мнемоническое правило: функции не должны по объему кода превышать двух экранов текста и иметь больше десяти локальных переменных. Каждая функция должна выполнять одно действие, но делать это хорошо. Не вредно разбить функцию на последовательность


Функции GMP

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

Функции GMP ПодразделыФункции Введение Функции этого вида позволяют работать с целыми числами повышенной точности определенного формата используя библиотеку GNU MP.Эта библиотека не входит в стандартный пакет PHP. Загрузить коды библиотеки и документацию по ней можно на


5.8.7 Функции

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

5.8.7 Функции СинтаксисОболочка bash позволяет пользователю создавать собственные функции. Функции ведут себя и используются точно так же, как обычные команды оболочки, т. е. мы можем сами создавать новые команды. Функции конструируются следующим образом: function name () {list}Причем


19.7.8. Функции

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

19.7.8. Функции Описание функции выглядит так: имя() { список; }Пример:cdir(){ # изменяем каталог cd / }При выполнении функция не создает нового процесса, а выполняется в среде процесса, содержащего эту функцию. Аргументы функции можно передать ей как обыкновенные параметры при


10.16 Функции TCP

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

10.16 Функции TCP Данная глава посвящена многочисленным функциям TCP. Ниже перечислены основные из них:? Связывание портов с соединениями? Инициализация соединений посредством трехшагового подтверждения? Выполнение медленного старта, исключающего перегрузку


8.6. Функции

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

8.6. Функции Оператор определения функции имеет следующий синтаксис:[function] имя() { список}Определять функцию можно в любом месте сценария, но вызов ее должен осуществляться строго после описания. Вызывается функция подобно любой команде — по имени. Переданные ей аргументы


3.1. Функции

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

3.1. Функции Пример 1.7: Функция вычисляющая факториал.VAR A, Y : INTEGER;FUNCTION FAKTORIAL (N : INTEGER) : INTEGER; VAR F, K : INTEGER; BEGIN F := 1; FOR K := 1 TO N DO F := F * K; FAKTORIAL := F END; BEGINWRITELN (‘ВВЕДИТЕ ЦЕЛОЕ ПОЛОЖИТЕЛЬНОЕ ЧИСЛО’);READLN (A);Y := FAKTORIAL (A);WRITELN (‘N!=’, Y);READLN;READLNEND.Обратите внимание на то, что в описании функции


3. Функции

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

3. Функции В C есть только функции, а процедур нет.Тело функции не может содержать в себе определения других функций.Функцию можно вызвать из другой функции.Оператор return возвращает выполнение программы в точку вызова функции.При использовании return; функция


4.5.3. Функции, которые создают новые конфигурации из существующих 4.5.3.1. Функции геометрии, которые производят новые конфигурации

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

4.5.3. Функции, которые создают новые конфигурации из существующих 4.5.3.1. Функции геометрии, которые производят новые конфигурации Раздел "4.5.2. Функции Geometry" обсуждает несколько функций, которые создают новые конфигурации из


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

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

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


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

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

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


Функции

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

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


Функции

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

Функции AddAtom Функция AddAtom добавляет строку символов в таблицу локальных атомов и возвращает уникальное значение (атом), идентифицирующее строку. ATOM AddAtom ( LPCTSTR lpString // указатель на добавляемую строку ); Параметры lpString - указатель на добавляемую строку, завершающуюся нулем.


Функции

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

Функции В табл. П3.1–П3.5 представлено описание наиболее часто используемых функций.Таблица П3.1. Булевые функции Функция Описание boolean boolean(object) Явным образом преобразует объект, который ей передается в булевый тип boolean not(boolean) Выполняет логическое