MurmurHash2



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[0]; k |= data[1] << 8; k |= data[2] << 16; k |= data[3] << 24; k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; data += 4; len -= 4; } switch (len) { case 3: h ^= data[2] << 16; case 2: h ^= data[1] << 8; case 1: h ^= data[0]; 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[2] << 16; case 2: t ^= data[1] << 8; case 1: t ^= data[0]; }; mmix(h,t); mmix(h,l); h ^= h >> 13; h *= m; h ^= h >> 15; return h; }