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

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

В разделе, посвященном хеш-таблицам, книги "Compilers: Principles, Techniques, and Tools" ("Компиляторы: принципы, технологии, инструменты"), Ахо (Aho) и других, которая была издана Addison-Wesley [2], описана функция хеширования, созданная П. Дж. Вайнбергером (P. J. Weinberger). Эту подпрограмму называют также хешем Executable and Linking Format (формат исполняемых и компонуемых модулей), или ELF-хешем. Используемый в ней алгоритм аналогичен тому, что применяется в подпрограмме листинга 7.1. Единственное исключение состоит в том, что в этом алгоритме реализован эффект рандомизации, когда операция XOR снова загружает старший полубайт действующей рабочей переменной хеша (полубайт, который должен исчезнуть в результате переполнения при выполнении следующей операции умножения), если он не равен нулю, в младшую часть переменной. Затем алгоритм устанавливает значение старшего полубайта равным нулю, в результате чего конечное хеш-значение всегда будет неотрицательным. (Исходный код функции можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshBse.pas.)

Листинг 7.2. Функция PJW хеширования строковых ключей

function TDPJWHash( const aKey : string;

aTableSize : integer): integer;

var

G : longint;

i : integer;

Hash : longint;

begin

Hash := 0;

for i := 1 to length (aKey) do

begin

Hash := (Hash shl 4) + ord(aKey[i]);

G := Hash and longint ($F0000000);

if (G <> 0) then

Hash := (Hash xor (G shr 24)) xor G;

end;

Result := Hash mod aTableSize;

end;

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

Мы не будем подробно останавливаться на других основных типах данных, поскольку в целом они успешно могут быть сведены к случаю целочисленных или строковых ключей. В качестве примера давайте рассмотрим хеширование дат, хранящихся в переменных TDateTime. В подавляющем большинстве приложений значения будут ограничиваться более поздними датами, чем заданная (например, 1 января 1975 года). В этом случае достаточно подходящей функцией хеширования была бы функция, выполняющая вычитание 1 января 1975 года из значения даты, для которого требуется получить хеш-значение, тем самым определяющая количество дней, истекших с момента начальной даты. Затем следует выполнить деление по модулю на размер хеш-таблицы.

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

Но предположим, что у нас имеется известный список 100 строковых ключей. Существует ли какая-либо функция хеширования, которая будет генерировать уникальное хеш-значение для каждого из этих известных ключей, чтобы можно было разработать хеш-функцию, содержащую ровно 100 элементов? Функции хеширования такого типа называют совершенными. Безусловно, теоретически это возможно. Существует очень много таких функций (по существу, это равнозначно определению перестановок исходных ключей). Но как найти одну из таких функций? К сожалению, ответ на данный вопрос выходит за рамки этой книги. Даже Кнут (Knuth) [13] обходит эту тему. На практике совершенные функции хеширования представляют лишь теоретический интерес. Как только возникает потребность в другом ключе, совершенная функция хеширования разрушается и нам приходится разрабатывать следующую. Значительно удобнее считать, что никаких совершенных функций хеширования не существует, и иметь дело с неизбежными конфликтами, которые будут периодически возникать.

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

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

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

Функции

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

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


Функции 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) Выполняет логическое