PJW-32

pjw 32 celsius, pjw 323
PJW-32 (hashpjw)

Создан

1980-е

Опубликован

1985

Размер хэша

32 бит

Тип

хеш-функция

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

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

Содержание

  • 1 История создания
  • 2 Алгоритм hashpjw
    • 2.1 Шаг 1
    • 2.2 Шаг 2
    • 2.3 Шаг 3
      • 2.3.1 Исходный текст
  • 3 Использование
  • 4 Примечания

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

Основная идея данной функции была разработана Питером Вэйнбергером (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 celsius, pjw 32 weeks, pjw 321gold, pjw 323


PJW-32 Информацию О

PJW-32


  • user icon

    PJW-32 beatiful post thanks!

    29.10.2014


PJW-32
PJW-32
PJW-32 Вы просматриваете субъект
PJW-32 что, PJW-32 кто, PJW-32 описание

There are excerpts from wikipedia on this article and video

Случайные Статьи

Анна-Павловна

Анна-Павловна

Анна-Павловна (нидерл. Anna Paulowna) — община и город в Нидерландах, в провинции Северная...
Белоспинный лори

Белоспинный лори

Систематика на Викивидах Изображения на Викискладе ITIS 554806 NCBI 176072 Межд...
Мартинес Сомало, Эдуардо

Мартинес Сомало, Эдуардо

Его Высокопреосвященство кардинал Эдуардо Мартинес Сомало (исп. Eduardo Martinez Somalo; род. 3...
Зенитная установка

Зенитная установка

Зенитная установка — общее название военной техники, предназначенной для ведения огня по воздуш...