FNV

FNV (англ. Fowler–Noll–Vo) — простая хеш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024-битных хешей.

Математическая запись

Функция FNV:

h = x n + 1 {displaystyle h=x_{n+1}} , x i + 1 = x i p ⊕ d i ( mod 2 32 ) {displaystyle x_{i+1}=x_{i}poplus d_{i}{pmod {2^{32}}}} , x 0 = 2166136261 {displaystyle x_{0}=2166136261} , p = 16777619 {displaystyle p=16777619} — простое число, d i {displaystyle d_{i}} — входная последовательность двоичных слов.

Модифицированная функция FNV:

h = x n + 1 {displaystyle h=x_{n+1}} , x i + 1 = ( x i ⊕ d i ) p ( mod 2 32 ) {displaystyle x_{i+1}=left(x_{i}oplus d_{i} ight)p{pmod {2^{32}}}} .

Пример кода

Функция проста в реализации. Её основа — умножение на простое число и сложение по модулю 2 с входным текстом.

const unsigned FNV_32_PRIME = 0x01000193; unsigned int FNV1Hash (char *buf) { unsigned int hval = 0x811c9dc5; // FNV0 hval = 0 while (*buf) { hval *= FNV_32_PRIME; hval ^= (unsigned int)*buf++; } return hval; }

Модификации

Существует модификация алгоритма, решающая некоторые его проблемы. В частности, проблему последнего байта. Весь смысл модификации — замена порядка операций на обратный. Сначала сложение, затем трансформация хеша (умножение на простое число).

Пример кода на C:

unsigned int FNV1aHash (char *buf) { unsigned int hval = 0x811c9dc5; while (*buf) { hval ^= (unsigned int)*buf++; hval *= FNV_32_PRIME; } return hval; }

Пример кода на Delphi:

function FNV1aHash(const buf; len: Integer): LongWord; var pb: PByte; i: Integer; begin pb := PByte(@buf); Result := $811C9DC5; for i := len downto 1 do begin Result := (Result xor pb^) * $01000193; Inc(pb); end; end;

Помимо вышеуказанной модификации были разработаны некоторые редакции алгоритма, улучшающие производительность. Примером таких функций являются FNV1A_Jesteress и FNV1A_Yorikke. Помимо работы над ускорением алгоритма, автор уделил внимание и качеству распределения.

Коллизии

Так как значение хеш-функции, приведённое в примере, 32-битное, вероятность появления коллизии значительно выше, чем у хеш-функций, возвращающих, к примеру, 128-битный хеш.