Хэш FNV-1 (32-бит) онлайн
Один из первых «быстрых» хэшей для хэш-таблиц — простое умножение и XOR по байтам. Считается прямо в браузере — текст никуда не отправляется.
Вычислить FNV-1 (32-бит)
Результат пересчитывается сам, пока вы печатаете. В режиме «По строкам» пустые строки тоже хэшируются — результат всегда совпадает по числу строк со входом. Нужна другая функция — на полной странице калькулятора их 32.
История FNV-1
FNV — расшифровывается по фамилиям авторов: Гленн Фаулер, Лэндон Кёрт Нолл и Ким-Пхонг Во. Алгоритм придумали в 1991 году как простой и быстрый хэш для хэш-таблиц — в те годы большинство таких функций либо были слишком медленными для реального времени, либо плохо распределяли ключи. FNV быстро разошёлся по компиляторам, языковым рантаймам и сетевым протоколам как «дефолтный простой хэш», когда криптографическая стойкость не нужна, а нужна скорость и хорошее распределение.
У FNV есть более новая версия — FNV-1a, отличающаяся только порядком двух операций в цикле, но дающая заметно лучшее распределение на коротких строках. Сегодня для новых проектов почти всегда рекомендуют именно FNV-1a; FNV-1 сохраняет значение в основном для совместимости со старым кодом.
Как устроен алгоритм
Схема предельно простая: заводится 32-битный аккумулятор, инициализированный «начальным значением» (offset basis) — числом 2166136261 (0x811c9dc5), подобранным авторами эмпирически для хорошего распределения. Затем для каждого байта строки выполняются две операции в фиксированном порядке: сначала умножение аккумулятора на «простое FNV» — 16777619 (0x01000193), тоже подобранное экспериментально, — а затем XOR с очередным байтом.
Характеристики
| Параметр | Значение |
|---|---|
| Длина хэша | 32 бита (8 hex-символов) |
| Операция на байт | умножение, затем XOR |
| Начальное значение | 0x811c9dc5 |
| Множитель (простое FNV) | 0x01000193 |
| Тип | Некриптографический хэш для хэш-таблиц |
| Придуман | 1991 |
Где применяется
- Хэш-таблицы и словари во многих языковых рантаймах и библиотеках
- Быстрая проверка на дубликаты, ключи кэша
- Некоторые сетевые протоколы и форматы, где нужен простой быстрый отпечаток
Криптостойкость
FNV-1 не проектировался как криптографический алгоритм: коллизии находятся легко, а без рандомизации начального значения хэш-таблицу на FNV можно намеренно «завалить» специально подобранными ключами (атака hash-flooding) — именно поэтому современные языки добавляют случайный seed к хэш-функциям, обрабатывающим недоверенный ввод.