MurmurHash2

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 6. června 2022; kontroly vyžadují 2 úpravy .

MurmurHash2  je jednoduchá a rychlá hašovací funkce pro obecné účely vyvinutá Austinem Applebym. Není kryptograficky zabezpečený , vrací 32bitové číslo bez znaménka .

Mezi výhody funkce autoři zařadili jednoduchost, dobré rozložení, silný lavinový efekt , vysokou rychlost a relativně vysokou odolnost proti kolizím . Aktuální verze algoritmu jsou optimalizovány pro procesory kompatibilní s Intel.

Ukázkový kód

unsigned int MurmurHash2 ( char * klíč , unsigned int len ​​​​) { const unsigned int m = 0x5bd1e995 ; const unsigned int seed = 0 ; const int r = 24 ; unsigned int h = semeno ^ len ; const unsigned char * data = ( const unsigned char * ) klíč ; bez znaménka int k = 0 ; zatímco ( 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 ; } vypínač ( len ) { případ 3 : h ^= data [ 2 ] << 16 ; případ 2 : h ^= data [ 1 ] << 8 ; případ 1 : h ^= data [ 0 ]; h *= m ; }; h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; návrat h ; }

MurmurHash 2A

Druhá verze hashovací funkce má některé nevýhody. Zejména se jedná o problém kolizí na malých strunách. Opravená verze má strukturu typu Merkle-Damgard , běží trochu pomaleji (asi o 20 %), ale vykazuje lepší statistiky.

#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 ; bez znaménka int l = len ; const unsigned char * data = ( const unsigned char * ) klíč ; unsigned int h = semeno ; bez znaménka int k ; zatímco ( len >= 4 ) { k = * ( unsigned int * ) data ; mmix ( h , k ); data += 4 ; len -= 4 ; } bez znaménka int t = 0 ; vypínač ( len ) { případ 3 : t ^= data [ 2 ] << 16 ; případ 2 : t ^= data [ 1 ] << 8 ; případ 1 : t ^= data [ 0 ]; }; mmix ( h , t ); mmix ( h , l ); h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; návrat h ; }

Odkazy