MurmurHash2

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 6. juni 2022; checks kræver 2 redigeringer .

MurmurHash2  er en enkel og hurtig hashfunktion til generelle formål udviklet af Austin Appleby. Ikke kryptografisk sikker , returnerer et 32-bit usigneret nummer.

Blandt fordelene ved funktionen bemærkede forfatterne enkelhed, god fordeling, kraftig lavineeffekt , høj hastighed og relativt høj modstandsdygtighed over for kollisioner . De nuværende versioner af algoritmen er optimeret til Intel -kompatible processorer.

Eksempelkode

usigneret int MurmurHash2 ( char * nøgle , usigneret int len ​​) { const unsigned int m = 0x5bd1e995 ; const unsigned int seed = 0 ; const int r = 24 ; usigneret int h = frø ^ len ; const unsigned char * data = ( const unsigned char * ) nøgle ; usigneret int k = 0 ; mens ( 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 ; } skifte ( len ) { tilfælde 3 : h ^= data [ 2 ] << 16 ; tilfælde 2 : h ^= data [ 1 ] << 8 ; tilfælde 1 : h ^= data [ 0 ]; h *= m ; }; h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; returnere h ; }

MurmurHash 2A

Den anden version af hash-funktionen har nogle ulemper. Dette er især problemet med kollisioner på små strenge. Den korrigerede version har en Merkle-Damgard type struktur , kører lidt langsommere (ca. 20%), men viser bedre statistik.

#define mmix(h,k) { k *= m; k ^= k >> r; k*=m; h *= m; h ^= k; } usigneret int MurmurHash2A ( const void * key , int len ​​, usigned int seed ) { const unsigned int m = 0x5bd1e995 ; const int r = 24 ; usigneret int l = len ; const unsigned char * data = ( const unsigned char * ) nøgle ; usigneret int h = frø ; usigneret int k ; mens ( len >= 4 ) { k = * ( unsigned int * ) data ; mmix ( h , k ); data += 4 ; len -= 4 ; } usigneret int t = 0 ; skifte ( len ) { tilfælde 3 : t ^= data [ 2 ] << 16 ; tilfælde 2 : t ^= data [ 1 ] << 8 ; tilfælde 1 : t ^= data [ 0 ]; }; mmix ( h , t ); mmix ( h , l ); h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; returnere h ; }

Links