PJW-32


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

Примечания


Wikimedia Foundation. 2010.

Смотреть что такое "PJW-32" в других словарях:

  • PJW — Preaching the Just Word (Community » Religion) …   Abbreviations dictionary

  • PJW — abbr. Pennsylvania Junior Wrestling …   Dictionary of abbreviations

  • Peter J. Weinberger — Peter Jay Weinberger is a computer scientist who works at Google.He received his PhD in mathematics (number theory) in 1969 from the University of California, Berkeley under Derrick Henry Lehmer for his thesis entitled Proof of a Conjecture of… …   Wikipedia

  • Acts of Union 1707 — The Acts of Union were a pair of Parliamentary Acts passed during 1706 and 1707 by the Parliament of England and the Parliament of Scotland to put into effect the terms of the Treaty of Union that had been agreed on July 22, 1706, following… …   Wikipedia

  • 1983 Cricket World Cup — Infobox cricket tournament name = 1983 Prudential Cup imagesize = 220px caption = administrator = International Cricket Council cricket format = One Day International tournament format = Round robin and Knockout host = England champions = India… …   Wikipedia

  • Vismon — was the Bell Labs system which displayed authors faces on one of their internal e mail systems. The name was a pun on the sysmon program used at Bell to show the load on computer systems. It can also be interpreted as visual monitor . The system… …   Wikipedia

  • Kyoko Nakajima — Born March 12, 1983 (1983 03 12) (age 28)[1] Saitama Prefecture, Japan Alias(es) Kyoko Nakashima Height 1.52 m (5 ft 0 in) …   Wikipedia

  • Companies listed on the New York Stock Exchange (M) — New York Stock Exchange listed stocks: 0 9 A B C D E F G H I J K L M N O P Q R S T U V W …   Wikipedia

  • Sons of the Thames — Infobox Rowing Club ClubName = Sons of the Thames Rowing Club Clubhouse BladeColour Emblem = Location = Hammersmith Coordinates = coord|51|29|25.4|N|0|14|19.6|W|region:GB scale:2000|display=title,inline|name=Sons of the Thames Rowing Club Founded …   Wikipedia

  • Crane vessel — Wind Lift I, Emden harbor, Emden, Germany …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.