FNV

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Математическая запись[править | править вики-текст]

Функция FNV:

h=x_{n+1},
x_{i+1} = x_i p \oplus d_i \pmod {2^{32}},
x_0=2 166 136 261,
p=16777619 — простое число,
d_i — входная последовательность двойных слов.

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

h=x_{n+1},
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-битный хеш.

Ссылки[править | править вики-текст]

Примечания[править | править вики-текст]