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; }

Ссылки

[править | править код]
Источник — https://ru.wikipedia.org/w/index.php?title=MurmurHash2&oldid=123129289