MurmurHash2

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 6. kesäkuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

MurmurHash2  on yksinkertainen ja nopea yleiskäyttöinen hash-funktio , jonka on kehittänyt Austin Appleby. Ei kryptografisesti turvallinen , palauttaa 32-bittisen allekirjoittamattoman numeron.

Toiminnon etujen joukossa kirjoittajat totesivat yksinkertaisuuden, hyvän jakelun, voimakkaan lumivyöryefektin , suuren nopeuden ja suhteellisen hyvän törmäyskestävyyden . Algoritmin nykyiset versiot on optimoitu Intel - yhteensopiville prosessoreille.

Esimerkkikoodi

unsigned int MurmurHash2 ( char * avain , unsigned int len ​​) { const unsigned int m = 0x5bd1e995 ; const unsigned int siemen = 0 ; const int r = 24 ; unsigned int h = siemen ^ len ; const unsigned char * data = ( const unsigned char * ) - avain ; etumerkitön int k = 0 ; kun ( 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 ; } kytkin ( len ) { tapaus 3 : h ^= data [ 2 ] << 16 ; tapaus 2 : h ^= data [ 1 ] << 8 ; tapaus 1 : h ^ = data [ 0 ]; h *= m ; }; h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; paluu h ; }

MurmurHash 2A

Hajautusfunktion toisella versiolla on joitain haittoja. Tämä on erityisesti pienten merkkijonojen törmäysongelma. Korjatussa versiossa on Merkle-Damgard- tyyppinen rakenne , se toimii hieman hitaammin (noin 20%), mutta näyttää paremmat tilastot.

#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 * ) - avain ; unsigned int h = siemen ; unsigned int k ; kun ( len >= 4 ) { k = * ( unsigned int * ) data ; mmix ( h , k ); data += 4 ; len - = 4 ; } etumerkitön int t = 0 ; kytkin ( len ) { tapaus 3 : t ^= data [ 2 ] << 16 ; tapaus 2 : t ^= data [ 1 ] << 8 ; tapaus 1 : t ^= data [ 0 ]; }; mmix ( h , t ); mmix ( h , l ); h ^= h >> 13 ; h *= m ; h ^= h >> 15 ; paluu h ; }

Linkit