FNV: различия между версиями
[отпатрулированная версия] | [отпатрулированная версия] |
Нет описания правки |
|||
Строка 1: | Строка 1: | ||
'''FNV''' ({{lang-en|Fowler–Noll–Vo}}) |
'''FNV''' ({{lang-en|Fowler–Noll–Vo}}) — простая хэш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024 — битных [[Хеш-сумма|хэшей]]. |
||
== Пример кода == |
== Пример кода == |
||
Функция проста в реализации. Ее основа |
Функция проста в реализации. Ее основа — умножение на простое число и сложение по модулю 2 с входным текстом. |
||
<source lang="C"> |
<source lang="C"> |
||
Строка 27: | Строка 27: | ||
== Модификации == |
== Модификации == |
||
Существует модификация алгоритма, решающая некоторые его проблемы. В частности, проблему последнего байта. Весь смысл модификации |
Существует модификация алгоритма, решающая некоторые его проблемы. В частности, проблему последнего байта. Весь смысл модификации — замена порядка операций на обратный. Сначала сложение, затем трансформация хэша (умножение на простое число). |
||
<source lang="C"> |
<source lang="C"> |
||
Строка 51: | Строка 51: | ||
== Коллизии == |
== Коллизии == |
||
Так как значение хэш-функции 32-битное, вероятность появления коллизии значительно выше, чем у хэш-функций, возвращающих, к примеру, 128-битный хэш. |
Так как значение хэш-функции 32-битное, вероятность появления коллизии значительно выше, чем у хэш-функций, возвращающих, к примеру, 128-битный хэш. |
||
=== Примеры коллизий === |
=== Примеры коллизий === |
Версия от 16:59, 9 октября 2010
FNV (англ. Fowler–Noll–Vo) — простая хэш-функция для общего применения, разработанная Гленом Фаулером, Лондоном Керт Нолом и Фогном Во. Не является криптографической функцией. Существуют варианты для 32-, 64-, 128-, 256-, 512-, и 1024 — битных хэшей.
Пример кода
Функция проста в реализации. Ее основа — умножение на простое число и сложение по модулю 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 ГРОБОКОПАТЕЛЬСТВО
Ссылки
- Хэш-функции общего назначения
- Исходные тексты хэш-функий общего назначения
- Страничка алгоритма (авторская)