FNV

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

Функция FNV:

${\displaystyle h=x_{n+1}}$,

${\displaystyle x_{i+1}=x_{i}p\oplus d_{i}{\pmod {2^{32}}}}$,

${\displaystyle x_{0}=2166136261}$,

${\displaystyle p=16777619}$ — простое число,

${\displaystyle d_{i}}$ — входная последовательность двоичных слов.

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

${\displaystyle h=x_{n+1}}$,

${\displaystyle x_{i+1}=\left(x_{i}\oplus d_{i}\right)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. Помимо работы над ускорением алгоритма, автор уделил внимание и качеству распределения^[1].

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

• Хеш-функции общего назначения
• Исходные тексты хеш-функций общего назначения
• Страничка алгоритма (авторская)
• Тестирование FNV и иных хеш-функций общего назначения на предмет коллизий и производительности