Читать на сайте.
Read on website.
Недавно на работе возникла задача: нужно было посчитать стабильный хэш объектов. Я сразу подумал про стандартные криптографические алгоритмы вроде SHA1, SHA256, SHA512 и MD5. Но у них есть два недостатка:
1. Хэш получается большим — от 160 до 512 бит.
2. Возвращается массив байтов, что означает лишние аллокации памяти.
Это подтолкнуло меня к поиску альтернатив. Так я быстро наткнулся на репозиторий xxHash и его реализацию на C#. Отличие xxHash в высокой скорости и возможности получить хэш в виде целого числа.
Важно понимать, что xxHash не криптографический алгоритм — он предназначен для других задач: быстрого хэширования, сравнения данных, создания ключей для кэшей или индексов.
Реализации в .NET
Для использования xxHash в своём приложении нужно установить пакет System.IO.Hashing. В нём есть 4 реализации алгоритма xxHash:
- XxHash32 (32 бита);
- XxHash64 (64 бита);
- XxHash3 (64 бита);
- XxHash128 (128 бит).
Производительность
Я сравнил эти алгоритмы по скорости расчёта хэша между собой. К сравнению также добавил алгоритмы SHA1, SHA2, SHA3 и MD5. Результаты оказались ожидаемыми (на обложке) — xxHash значительно быстрее остальных.
Пример использования
xxHash особенно удобен благодаря следующим фишкам:
– Метод
Append. Он позволяет поэтапно добавлять данные к расчёту хэша без промежуточных аллокаций. – Хэш в виде числа. В зависимости от алгоритма можно получить хэш как
uint, ulong или UInt128, без массива байтов. – Поддержка работы со
Span<T>. Можно использовать стек вместо кучи и избежать лишних аллокаций.Пример реализации расчёта хэша с xxHash на второй картинке.
Выводы
Использование xxHash для расчёта стабильного хэша позволяет:
– Быстро рассчитать хэш. Это один из самых быстрых алгоритмов.
– Избежать аллокаций. Используя
Span и Append, можно рассчитывать хэш, используя только стек и регистры.– Хранить хэш как
uint или ulong. Это всего 4 и 8 байт соответственно. Такие значения хорошо индексируются БД и позволяют упростить структуру SQL запросов. Вместо сложных запросов с множеством условий, можно искать по одному полю: WHERE Hash = ... Это особенно полезно при работе с таблицами, где сотни миллионов строк.