PJW-32

Криптографическая хеш-функция
Название	PJW-32 (hashpjw)
Создан	1980-е
Опубликован	1985
Размер хеша	32 бит
Тип	хеш-функция

PJW-32 (hashpjw) — хеш-функция, разработанная Питером Вэйнбергером (Peter J. Weinberger) из AT&T Bell Laboratories.

Для произвольного входного сообщения функция генерирует 32-разрядное хеш-значение, называемое хеш-суммой сообщения. Этот алгоритм используется в хеш-таблицаx и декартовых деревьях, а также в процедурах проверки регистрационных ключей при защите программного обеспечения. В настоящее время эта функция используется в формате файла ELF Linux, выбранном стандартом бинарных файлов в Unix-подобных системах.

История создания

Основная идея данной функции была разработана Питером Вэйнбергером (Peter J. Weinberger)в 80-е годы, во время его работы в AT&T Bell Laboratories в рамках создания его собственного компилятора для языка C. Так как функция в основном используется в хеш-таблицаx, она имеет множество модификаций, в зависимости от специфики определённой таблицы, операционной системы, структуры хешируемых данных и т. д.

Впервые упоминание о данной функции встречается в книге Альфреда Ахо, Рави Сети и Джеффри Ульмана «Компиляторы. Принципы, технологии, инструменты» в 1985 году. В ней говорится о явном превосходстве данной функции над другими, используемыми в области организации поиска с помощью создания хеш-таблиц. В частности, приводится одна из модификаций для таблицы размером в 211 списков, а также сравнительные характеристики данной модификации.

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

В настоящее время одна из модификаций — ELFhash широко распространена, так как используется в формате файлов ELF. Данный формат был впервые опубликован в версии операционный системы unix System V. Вскоре, после этого, он был принят многими производителями unix-подобных систем, и в 1999 году был выбран как стандарт формата бинарных файлов для всех Unix и Unix-подобных систем на платформе x86.

Алгоритм hashpjw

В изначальном варианте, алгоритм был адаптирован на работу с хеш-таблицами, то есть на начальной стадии имелось сообщение s произвольной длины L, от которого требовалось найти хеш значение h. Перед вычислением значение h устанавливается в 0. Сообщение считывается посимвольно. Число m — предполагаемый размер таблицы.

Шаг 1

Каждый считанный символ с сообщения s переводится в число, а затем рассматривается его битовое значение. Преобразование отдельного символа в целое число обычно поддерживается языками программирования. Например, Pascal предоставляет для этого функцию ord (или прямое приведение к типу byte), а С автоматически преобразовывает символ в целое число при выполнении арифметических операций.
Для полученного значения с производится сдвиг h на 4 позиции влево и суммирование с с.

Шаг 2

Производится проверка: если любой из 4 старших битов h равен 1 то сдвигаем их вправо на 24 позиции. Затем выполняем операцию исключающего или со значением h и сбрасываем значения 4 старших битов в 0.

Шаг 3

После проведения шагов 1-2 со всеми символами сообщения s, производится деление h по модулю m. Полученное число — это номер списка в таблице, к которому следует присоединить данную строку.

Исходный текст

unsigned int PJWHash (char *str, unsigned int len)
{
        unsigned int hash = 0;
        unsigned int test = 0;
        unsigned int i = 0;
 
        for (i = 0; i < len; str++, i++) {
                hash = (hash << 4) + (unsigned char)(*str);
 
                if ((test = hash & 0xf0000000) != 0) {
                        hash = ((hash ^ (test >> 24)) & (0xfffffff));
                }
        }
        return hash;
}

Использование

Основное использование хеш-функции hashpjw и большинства её модификаций это хеш-таблицы. Использование данной хеш-функции полностью обосновано,^[кем?] несмотря на большое наличие коллизий. hashpjw является быстродействующей, так как выполняет только поразрядные операции, то есть не выполняется никаких сложных арифметических действий.

Примечания

Для улучшения этой статьи желательно?: Добавить иллюстрации. Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Проставить интервики в рамках проекта Интервики.