WikiSort.ru - Не сортированное

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 — предполагаемый размер таблицы.

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

Примечания

В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 19 июня 2018 года.