MurmurHash¶

MurmurHash — это семейство не криптографических хэш-функций, разработанных Остином Эпплби (Austin Appleby) в 2008 году. Функции предназначены для быстрого вычисления хэш-кода (обычно 32- или 128-битного) из произвольного набора входных данных. Основными характеристиками MurmurHash являются высокая скорость работы, хорошее распределение значений (низкая коллизионность) и простота реализации. Название происходит от слов «murmur» (бормотание) и «hash» (хэш), что отражает простой и «бормочущий» характер внутренних операций.

¶История

MurmurHash была создана Остином Эпплби в 2008 году как альтернатива существующим не криптографическим хэш-функциям, таким как Jenkins hash и FNV hash, которые не всегда обеспечивали достаточную скорость и качество распределения на современных процессорах. Первая версия, MurmurHash1, была опубликована в 2008 году. В 2009 году вышла версия MurmurHash2, которая значительно улучшила производительность и качество хэширования. В 2010 году была выпущена MurmurHash3, ставшая наиболее распространённой версией. Она включает в себя 32-битный и 128-битный варианты, а также оптимизированные реализации для x86 и x86-64 архитектур. В 2015 году Эпплби объявил о прекращении активной разработки, но MurmurHash остаётся широко используемой в индустрии.

¶Алгоритм работы

MurmurHash относится к классу хэш-функций, основанных на операциях умножения, сдвига и XOR. Алгоритм обрабатывает входные данные блоками фиксированного размера (обычно 4 байта для 32-битной версии). Основные этапы работы:

1. Инициализация: Устанавливается начальное значение хэша (seed), которое может быть произвольным целым числом. Это позволяет получать разные хэш-коды для одних и тех же данных, используя разные seed.
2. Обработка блоков: Каждый блок данных обрабатывается с помощью последовательности операций:

• Умножение на константу (например, c1 = 0xcc9e2d51 и c2 = 0x1b873593 для 32-битной версии).
• Циклический сдвиг влево (ROL).
• Операция XOR с текущим значением хэша.
• Умножение на другую константу.

1. Обработка хвоста: Если длина входных данных не кратна размеру блока, оставшиеся байты обрабатываются отдельно, с использованием аналогичных операций, но с учётом их меньшего размера.
2. Финальное перемешивание: После обработки всех данных выполняется серия операций XOR и сдвигов для улучшения распределения битов в итоговом хэш-коде. Это включает в себя:

• XOR с длиной входных данных.
• Операция h ^= h >> 16.
• Умножение на константу 0x85ebca6b.
• Операция h ^= h >> 13.
• Умножение на константу 0xc2b2ae35.
• Операция h ^= h >> 16.

¶Версии и варианты

¶MurmurHash1

Первая версия, опубликованная в 2008 году. Имела ограниченное распространение и была быстро заменена улучшенными версиями.

¶MurmurHash2

Вторая версия, выпущенная в 2009 году. Включала 32-битный и 64-битный варианты. Отличалась от первой версии улучшенной производительностью и более качественным распределением. Однако в 2010 году были обнаружены некоторые коллизии, что привело к созданию MurmurHash3.

¶MurmurHash3

Третья и наиболее распространённая версия, выпущенная в 2010 году. Включает три основных варианта:

• MurmurHash3_x86_32: 32-битный хэш, оптимизированный для 32-битных процессоров.
• MurmurHash3_x86_128: 128-битный хэш, оптимизированный для 32-битных процессоров.
• MurmurHash3_x64_128: 128-битный хэш, оптимизированный для 64-битных процессоров.

MurmurHash3 считается эталоном для не криптографических хэш-функций благодаря сочетанию скорости и качества.

¶Характеристики

¶Скорость

MurmurHash является одной из самых быстрых не криптографических хэш-функций. Она использует простые арифметические операции (умножение, сдвиг, XOR), которые хорошо поддерживаются современными процессорами. В тестах производительности MurmurHash3 часто превосходит такие функции, как MD5, SHA-1, SHA-256, а также другие не криптографические функции, такие как FNV и Jenkins.

¶Качество распределения

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

¶Устойчивость к коллизиям

Хотя MurmurHash не является криптографической функцией и не предназначена для защиты от атак, она обладает высокой устойчивостью к случайным коллизиям. Вероятность коллизии для 32-битного хэша составляет примерно 1/2^32, а для 128-битного — 1/2^128. Однако для 32-битного хэша при большом количестве элементов (более 10^5) коллизии становятся вероятными.

¶Seed

MurmurHash поддерживает параметр seed (начальное значение), что позволяет получать разные хэш-коды для одних и тех же данных. Это полезно для предотвращения атак, основанных на предсказуемости хэш-кодов, например, в хэш-таблицах.

¶Применение

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

¶Хэш-таблицы

MurmurHash является одной из самых популярных хэш-функций для реализации хэш-таблиц в языках программирования и базах данных. Она используется в:

• Python: В стандартной библиотеке Python (начиная с версии 3.4) для хэширования строк используется алгоритм, основанный на MurmurHash.
• Java: В некоторых реализациях HashMap (например, в Apache Harmony) используется MurmurHash.
• C++: В библиотеках, таких как std::unordered_map, часто используется MurmurHash в качестве хэш-функции по умолчанию.
• Redis: В распределённом кэше Redis используется MurmurHash для распределения ключей по узлам кластера.

¶Распределённые системы

MurmurHash применяется в алгоритмах консистентного хэширования, используемых в распределённых кэшах (Memcached, Redis), базах данных (Cassandra, DynamoDB) и системах распределённых файлов (HDFS). Консистентное хэширование позволяет минимизировать количество перемещаемых данных при добавлении или удалении узлов.

¶Проверка целостности данных

MurmurHash может использоваться для быстрой проверки целостности данных, например, при сравнении файлов или блоков данных. Однако для этой цели не рекомендуется использовать её в криптографических приложениях, так как она не устойчива к коллизионным атакам.

¶Генерация случайных чисел

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

¶Анализ данных

В задачах дедупликации данных, поиска дубликатов и кластеризации MurmurHash используется для быстрого сравнения больших объёмов данных.

¶Критика и ограничения

¶Не криптографическая стойкость

Основным ограничением MurmurHash является отсутствие криптографической стойкости. Она не предназначена для защиты от атак, направленных на нахождение коллизий или восстановление исходных данных. Для криптографических целей (например, хэширование паролей, цифровые подписи) следует использовать функции семейства SHA-2 или SHA-3.

¶Коллизии для 32-битного хэша

32-битный хэш (MurmurHash3_x86_32) имеет ограниченное пространство значений (2^32). При большом количестве входных данных (например, более 10^5 элементов) вероятность коллизий становится значительной, что может привести к деградации производительности хэш-таблиц.

¶Зависимость от архитектуры

Реализации MurmurHash могут быть оптимизированы под конкретную архитектуру процессора (x86, x86-64). Это может приводить к различиям в производительности на разных платформах.

¶Устаревание

Хотя MurmurHash3 остаётся популярной, существуют более современные не криптографические хэш-функции, такие как xxHash, CityHash и FarmHash, которые могут превосходить её по скорости или качеству распределения в некоторых сценариях.

¶Примеры реализации

¶Пример на языке C (32-битная версия MurmurHash3)

```c uint32_t murmur3_32(const void key, int len, uint32_t seed) { const uint8_t data = (const uint8_t)key; const int nblocks = len / 4; uint32_t h1 = seed; const uint32_t c1 = 0xcc9e2d51; const uint32_t c2 = 0x1b873593; const uint32_t blocks = (const uint32_t )(data + nblocks 4);

for (int i = -nblocks; i; i++) { uint32_t k1 = blocks[i]; k1 = c1; k1 = (k1 << 15) | (k1 >> 17); k1 = c2; h1 ^= k1; h1 = (h1 << 13) | (h1 >> 19); h1 = h1 * 5 + 0xe6546b64; }

const uint8_t tail = (const uint8_t )(data + nblocks * 4); uint32_t k1 = 0;

switch (len & 3) { case 3: k1 ^= tail[2] << 16; case 2: k1 ^= tail[1] << 8; case 1: k1 ^= tail[0]; k1 = c1; k1 = (k1 << 15) | (k1 >> 17); k1 = c2; h1 ^= k1; }

h1 ^= len; h1 ^= h1 >> 16; h1 = 0x85ebca6b; h1 ^= h1 >> 13; h1 = 0xc2b2ae35; h1 ^= h1 >> 16;

return h1; } ```

¶Источники

1. Appleby, Austin. «MurmurHash». GitHub. 2008–2010.
2. Appleby, Austin. «MurmurHash3». GitHub. 2010.
3. «MurmurHash». Wikipedia. 2023.
4. «MurmurHash3». Open Source Implementations. 2010–2023.
5. «Hash Functions». Python Documentation. 2014.
6. «Consistent Hashing». Redis Documentation. 2015.