Hash

FNV

FNV (Fowler–Noll–Vo) — это семейство хэш-функций, широко используемых для быстрого вычисления хэш-кодов строк и других данных. FNV-1 и FNV-1a — это две основные версии этого алгоритма. Они применяются для создания хэш-таблиц, проверки целостности данных и в других ситуациях, где требуется быстрый и простой способ создания уникальных идентификаторов для данных.

Основные характеристики FNV

1. FNV-1: Хэш вычисляется путем последовательного умножения каждого байта данных на константу, а затем выполнения операции побитового XOR с текущим значением хэша.
2. FNV-1a: Порядок операций изменен: сначала выполняется операция XOR с текущим значением хэша, а затем умножение на константу.

Формулы

• FNV-1:

  hash = offset_basis
  for each byte_of_data to be hashed
      hash = hash * FNV_prime
      hash = hash ^ byte_of_data
  

• FNV-1a:

  hash = offset_basis
  for each byte_of_data to be hashed
      hash = hash ^ byte_of_data
      hash = hash * FNV_prime
  

Варианты по размеру хэша

FNV поддерживает несколько различных размеров хэш-кодов, что определяет количество бит в итоговом хэше:

• FNV-1 32-bit (FNV-1 32): Хэш-код длиной 32 бита.
• FNV-1 64-bit (FNV-1 64): Хэш-код длиной 64 бита.
• FNV-1 128-bit (FNV-1 128): Хэш-код длиной 128 бит.

Каждая из этих версий также имеет аналогичную версию с суффиксом "a" (FNV-1a), которая использует слегка измененный порядок операций.

Отличия между FNV-1 и FNV-1a

• FNV-1: Использует умножение перед побитовым XOR.
• FNV-1a: Сначала выполняется операция XOR, затем умножение.

Выбор между FNV-1 и FNV-1a

• FNV-1a имеет тенденцию давать лучшее распределение хэшей и уменьшает количество коллизий в некоторых случаях, что делает его предпочтительным вариантом для большинства применений.

Примеры применения

• Хэш-таблицы
• Проверка целостности данных
• Уникальные идентификаторы
• Индексация строк и других данных

Примеры FNV-констант

• 32-bit:

  • Offset basis: 2166136261
  • FNV prime: 16777619

• 64-bit:

  • Offset basis: 14695981039346656037
  • FNV prime: 1099511628211

• 128-bit:

  • Offset basis: 144066263297769815596495629667062367629
  • FNV prime: 309485009821345068724781371

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

Выбор размера хэш-кода

Выбор размера хэш-кода (32, 64, 128 бит и т.д.) зависит от нескольких факторов, включая требования к распределению хэшей, объем данных и доступную память. Вот основные рекомендации по выбору размера хэш-кода:

FNV-1 32-bit (или FNV-1a 32-bit)

• Когда использовать:

  • Подходит для небольших объемов данных и случаев, когда количество уникальных значений относительно невелико.
  • Используется в системах с ограниченной памятью, где каждый байт на счету.
  • Применяется в системах, где небольшие размеры хэш-кодов достаточно для предотвращения большого числа коллизий.

• Примеры применения:

  • Небольшие хэш-таблицы
  • Кеширование небольших объемов данных
  • Уникальные идентификаторы в ограниченных системах (например, встроенные системы)

FNV-1 64-bit (или FNV-1a 64-bit)

• Когда использовать:

  • Подходит для более крупных объемов данных и случаев, когда нужно уменьшить вероятность коллизий по сравнению с 32-битной версией.
  • Применяется в системах, где необходимо лучшее распределение хэшей и большая устойчивость к коллизиям.
  • Идеально для приложений, работающих с большим количеством уникальных значений.

• Примеры применения:

  • Средние и большие хэш-таблицы
  • Файловые системы и базы данных, где требуется высокая надежность
  • Кеширование данных в веб-серверах и других системах с высоким трафиком

FNV-1 128-bit (или FNV-1a 128-bit)

• Когда использовать:

  • Подходит для очень больших объемов данных, где требуется минимизировать вероятность коллизий.
  • Используется в системах, где необходимо работать с огромными объемами уникальных данных.
  • Применяется для задач, требующих высокой степени уникальности хэшей, таких как криптография или распределенные системы.

• Примеры применения:

  • Очень большие хэш-таблицы
  • Криптографические приложения и задачи, требующие высокой надежности
  • Глобальные системы идентификации и распределенные базы данных

Общие рекомендации

• 32-битные хэши: Подходят для небольших приложений и систем с ограниченной памятью. Идеальны для хэш-таблиц, содержащих тысячи или десятки тысяч записей.
• 64-битные хэши: Хороший компромисс между производительностью и вероятностью коллизий. Подходят для большинства современных приложений, требующих хэширования данных.
• 128-битные хэши: Используются для задач с высокими требованиями к уникальности и распределению хэшей, особенно в больших и распределенных системах.

При выборе размера хэш-кода важно учитывать конкретные требования вашего приложения, объем данных и допустимую вероятность коллизий. В большинстве случаев 64-битный хэш будет достаточно хорошим выбором, предоставляя хорошее распределение хэшей и устойчивость к коллизиям при умеренных объемах данных.