PJW-32

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

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

Для произвольного входного сообщения функция генерирует 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, int m)
{
	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 % m;
}

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

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

Примечания

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.