Хеш функция Дженкинса | это... Что такое Хеш функция Дженкинса? (original) (raw)

Хэш-функции Дженкинса представляют собой семейство хэш-функций общего назначения для ключей переменной длины разработанных Бобом Дженкинсом. Функции также могут использоваться в качестве контрольной суммы для обнаружения случайного повреждения данных или обнаружения идентичных записей в базе данных. Впервые описание функции было опубликовано в 1997 году.

Содержание

• 1 Хэш-функции
  • 1.1 one-at-a-time
  • 1.2 lookup2
  • 1.3 lookup3
• 2 Ссылки

Хэш-функции

one-at-a-time

Приведенный текст функции взят с веб-страницы Боба Дженкинса и является расширенной версией, опубликованной автором в журнале доктора Доббса.

uint32_t jenkins_one_at_a_time_hash(char *key, size_t len) { uint32_t hash, i; for(hash = i = 0; i < len; ++i) { hash += key[i]; hash += (hash << 10); hash ^= (hash >> 6); } hash += (hash << 3); hash ^= (hash >> 11); hash += (hash << 15); return hash; }

Иллюстрация лавинного эффекта функции Дженкинса с использованием функции one-at-a-time для хеширования 3-байтовых ключей.

На рисунке справа показан лавинный эффект функции.

Каждая из 24 строк соответствует одному биту в 3-байтовом ключе на входе, и каждый из 32 столбцов соответствует биту в выходном хеше. Цвета показывают насколько хорошо входной бит влияет на данный бит на выходе: зеленый квадрат указывает хорошее перемешивание, желтый квадрат слабое перемешивание, и красный обозначал бы, что перемешивания не происходит. Как видно из рисунка, только несколько битов в последнем байте входного ключа слабо перемешаны с несколькими битами результата.

lookup2

Функция lookup2 была промежуточным вариантом функции one-at-a-time.

lookup3

Функция lookup3 разбивает вход на блоки по 12 байт в каждом (96 бит).[1] Такое поведение может быть более целесообразным, когда скорость важнее, чем простота. Имейте в виду, что увеличение скорости работы при использовании этого варианта хэша вероятно только для больших ключей, и что повышенная сложность реализации наоборот может вызвать замедление работы. Например, вследствие того, что компилятор может оказаться не в состоянии подставить функцию инлайн.

Ссылки

1. ↑ Боб Дженкинс, lookup3.c исходный код. На 16 апреля 2009 года.

Хеш-функции
Общего назначения	Adler-32 • CRC • FNV • Murmur2 • PJW-32 • TTH • Jenkins hash
Криптографические	JH • HAVAL • Keccak • LM-хеш • MD2 • MD4 • MD5 • MD6 • N-Hash • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 • SHA-1 • SHA-2 • Skein • Snefru • Tiger • Whirlpool • ГОСТ Р 34.11-94