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

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

Оглавление книги