PJW-32

	Криптографическая</br>хеш-функция
Название	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 hash = 0;
	unsigned int test = 0;
 
	for (; *str; str++) {
		hash = (hash << 4) + (unsigned char)(*str);
 
		if ((test = hash & 0xf0000000) != 0) {
			hash = ((hash ^ (test >> 24)) & (0xfffffff));
		}
	}
	return hash;
}

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

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

Напишите отзыв о статье "PJW-32"

Примечания

Отрывок, характеризующий PJW-32

Граф Илья Андреич, сладко улыбаясь, одобрительно кивал головой.
– И что же, разве наши ополченцы составили пользу для государства? Никакой! только разорили наши хозяйства. Лучше еще набор… а то вернется к вам ни солдат, ни мужик, и только один разврат. Дворяне не жалеют своего живота, мы сами поголовно пойдем, возьмем еще рекрут, и всем нам только клич кликни гусай (он так выговаривал государь), мы все умрем за него, – прибавил оратор одушевляясь.
Илья Андреич проглатывал слюни от удовольствия и толкал Пьера, но Пьеру захотелось также говорить. Он выдвинулся вперед, чувствуя себя одушевленным, сам не зная еще чем и сам не зная еще, что он скажет. Он только что открыл рот, чтобы говорить, как один сенатор, совершенно без зубов, с умным и сердитым лицом, стоявший близко от оратора, перебил Пьера. С видимой привычкой вести прения и держать вопросы, он заговорил тихо, но слышно:
– Я полагаю, милостивый государь, – шамкая беззубым ртом, сказал сенатор, – что мы призваны сюда не для того, чтобы обсуждать, что удобнее для государства в настоящую минуту – набор или ополчение. Мы призваны для того, чтобы отвечать на то воззвание, которым нас удостоил государь император. А судить о том, что удобнее – набор или ополчение, мы предоставим судить высшей власти…
Пьер вдруг нашел исход своему одушевлению. Он ожесточился против сенатора, вносящего эту правильность и узкость воззрений в предстоящие занятия дворянства. Пьер выступил вперед и остановил его. Он сам не знал, что он будет говорить, но начал оживленно, изредка прорываясь французскими словами и книжно выражаясь по русски.
– Извините меня, ваше превосходительство, – начал он (Пьер был хорошо знаком с этим сенатором, но считал здесь необходимым обращаться к нему официально), – хотя я не согласен с господином… (Пьер запнулся. Ему хотелось сказать mon tres honorable preopinant), [мой многоуважаемый оппонент,] – с господином… que je n'ai pas L'honneur de connaitre; [которого я не имею чести знать] но я полагаю, что сословие дворянства, кроме выражения своего сочувствия и восторга, призвано также для того, чтобы и обсудить те меры, которыми мы можем помочь отечеству. Я полагаю, – говорил он, воодушевляясь, – что государь был бы сам недоволен, ежели бы он нашел в нас только владельцев мужиков, которых мы отдаем ему, и… chair a canon [мясо для пушек], которую мы из себя делаем, но не нашел бы в нас со… со… совета.
Многие поотошли от кружка, заметив презрительную улыбку сенатора и то, что Пьер говорит вольно; только Илья Андреич был доволен речью Пьера, как он был доволен речью моряка, сенатора и вообще всегда тою речью, которую он последнею слышал.
– Я полагаю, что прежде чем обсуждать эти вопросы, – продолжал Пьер, – мы должны спросить у государя, почтительнейше просить его величество коммюникировать нам, сколько у нас войска, в каком положении находятся наши войска и армии, и тогда…
Но Пьер не успел договорить этих слов, как с трех сторон вдруг напали на него. Сильнее всех напал на него давно знакомый ему, всегда хорошо расположенный к нему игрок в бостон, Степан Степанович Апраксин. Степан Степанович был в мундире, и, от мундира ли, или от других причин, Пьер увидал перед собой совсем другого человека. Степан Степанович, с вдруг проявившейся старческой злобой на лице, закричал на Пьера:
– Во первых, доложу вам, что мы не имеем права спрашивать об этом государя, а во вторых, ежели было бы такое право у российского дворянства, то государь не может нам ответить. Войска движутся сообразно с движениями неприятеля – войска убывают и прибывают…
Другой голос человека, среднего роста, лет сорока, которого Пьер в прежние времена видал у цыган и знал за нехорошего игрока в карты и который, тоже измененный в мундире, придвинулся к Пьеру, перебил Апраксина.
– Да и не время рассуждать, – говорил голос этого дворянина, – а нужно действовать: война в России. Враг наш идет, чтобы погубить Россию, чтобы поругать могилы наших отцов, чтоб увезти жен, детей. – Дворянин ударил себя в грудь. – Мы все встанем, все поголовно пойдем, все за царя батюшку! – кричал он, выкатывая кровью налившиеся глаза. Несколько одобряющих голосов послышалось из толпы. – Мы русские и не пожалеем крови своей для защиты веры, престола и отечества. А бредни надо оставить, ежели мы сыны отечества. Мы покажем Европе, как Россия восстает за Россию, – кричал дворянин.