FNV

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 \left( \mod 2^{32} \right),
x_0=2 166 135 261,
p=16777619 — простое число,
d_i — входная последовательность двойных слов.

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

h=x_{n+1},
x_{i+1} = \left( x_i \oplus d_i \right) p \left( \mod 2^{32} \right).

Пример кода

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

#define FNV_32_PRIME ((unsigned int)0x01000193)
 
unsigned int FNV1Hash (char *buf, unsigned int len)
{
  unsigned char *bp = (unsigned char *)buf;     
  unsigned char *be = bp + len;         
  unsigned int hval = 0x811c9dc5;
 
  while (bp < be)
    {
      hval *= FNV_32_PRIME;
      hval ^= (unsigned int)*bp++;
    }
 
  return hval;
}

Модификации

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

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

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

Коллизии

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

Примеры коллизий

 62274fb9:   ИЗБИТЫЕ
             НЕВЗНАЧАЙ

 65194ecd:   EKSISTENCIALIZEM
             ГРОБОКОПАТЕЛЬСТВО

Ссылки

Примечания


Wikimedia Foundation. 2010.

Поможем решить контрольную работу

Полезное


Смотреть что такое "FNV" в других словарях:

  • FNV — could stand for: *Federatie Nederlandse Vakbeweging, Netherlands, (Federated Netherlands Labour Movement) *Förbundet Nordisk Vuxenupplysning, Sweden, (Nordic Association of Adult Education) *Foreningen Naturparkens Venner, Denmark *Fowler Noll Vo …   Wikipedia

  • FNV — Die Abkürzung FNV wird in folgenden Zusammenhängen verwendet: Federatie Nederlandse Vakbeweging (niederländischer Gewerkschaftsbund) In der Informatik: ein Algorithmus zur Generierung von Streuwerten über Datenfelder steht in der Neurologie für… …   Deutsch Wikipedia

  • Fnv — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres    …   Wikipédia en Français

  • FNV — FiNova Group, Inc. (Business » NYSE Symbols) …   Abbreviations dictionary

  • FNV PA — FiNova Group, Inc., Financial Trust (Business » NYSE Symbols) …   Abbreviations dictionary

  • FNV — 1) Fremdrenten Nachversicherungs Verordnung EN Ordinance on Additional Social Insurance Pensions for Refugees 2) Finger Nasenversuch EN finger to nose maneuver (med.) 3) Fachnormenausschuß Vakuumtechnik EN Technical Standards Committee for Vacuum …   Abkürzungen und Akronyme in der deutschsprachigen Presse Gebrauchtwagen

  • FNV — abbr. Field Not Valid …   Dictionary of abbreviations

  • FNV Mondiaal — is the international arm of FNV (Federation Dutch Labour Movement) …   Wikipedia

  • FNV (Informatik) — In der Informatik ist FNV ein Algorithmus zur Generierung von Streuwerten über Datenfelder: eine sog. Hash Funktion. Nachnamensgeber des Kürzels FNV sind Glenn Fowler, Curt Landon Noll und Phong Vo, die den Algorithmus in Kooperation entwickelten …   Deutsch Wikipedia

  • Clase Almirante Clemente — FNV Almirante Clemente (D 12) ABRV GHQ 11 Almirante Clemente Guardacostas de Altura Almirante Clemente Banderas …   Wikipedia Español


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»