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

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

Функция FNV:

,

,

,

— простое число,

— входная последовательность двойных слов.

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

,

.

Пример кода

Функция проста в реализации. Ее основа — умножение на простое число и сложение по модулю 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;
}

Коллизии

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

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

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

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

Ссылки

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

Примечания