MurmurHash2 — простая и быстрая хеш-функция общего назначения, разработанная Остином Эпплби. Не является криптографически-безопасной, возвращает 32-разрядное беззнаковое число.
Из достоинств функции авторами отмечена простота, хорошее распределение, мощный лавинный эффект, высокая скорость и сравнительно высокая устойчивость к коллизиям. Текущие версии алгоритма оптимизированы под Intel-совместимые процессоры.
Пример кода
unsigned int MurmurHash2 (char * key, unsigned int len) { const unsigned int m = 0x5bd1e995; const unsigned int seed = 0; const int r = 24;
unsigned int h = seed ^ len;
const unsigned char * data = (const unsigned char *)key; unsigned int k = 0;
while (len >= 4)
k = data; k |= data << 8; k |= data << 16; k |= data << 24;
k *= m; k ^= k >> r; k *= m;
h *= m; h ^= k;
data += 4; len -= 4;
switch (len)
case 3: h ^= data << 16; case 2: h ^= data << 8; case 1: h ^= data; h *= m;
h ^= h >> 13; h *= m; h ^= h >> 15;
return h; }
MurmurHash 2A
Вторая версия хеш-функции имеет некоторые недостатки. В частности, это проблема коллизий на небольших строках. Исправленный вариант имеет структуру типа Merkle-Damgard, выполняется немного медленнее (примерно на 20 %), но показывает лучшую статистику.
#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; }
unsigned int MurmurHash2A ( const void * key, int len, unsigned int seed ) { const unsigned int m = 0x5bd1e995; const int r = 24; unsigned int l = len;
const unsigned char * data = (const unsigned char *)key;
unsigned int h = seed; unsigned int k;
while(len >= 4) { k = *(unsigned int*)data;
mmix(h,k);
data += 4; len -= 4;
unsigned int t = 0;
switch(len) { case 3: t ^= data << 16; case 2: t ^= data << 8; case 1: t ^= data;
mmix(h,t); mmix(h,l);
h ^= h >> 13; h *= m; h ^= h >> 15;
return h; }
Ссылки Хеш-функции общего назначения Исходные тексты хеш-функций общего назначения Страничка функции Статистика коллизий MurmurHash и её модификация Статистика производительности популярных хеш-функций