Por favor explique murmur hash?

Acabo de descubrir el murmullo hash, parece ser el más rápido conocido y bastante resistente a las colisiones. Traté de profundizar más sobre el algoritmo o la implementación en el código fuente completo, pero estoy teniendo dificultades para entenderlo. ¿Podría alguien aquí explicar el algoritmo utilizado, o implementarlo en el código fuente completo, preferiblemente en C. Leo el código fuente C desde el sitio web del autor, pero no tiene idea, como: ¿qué es semilla, h, k, m? ¿qué significa esto:Por favor explique murmur hash?

k *= m; 
k ^= k >> r; 
k *= m; 

h *= m; 
h ^= k; 

data += 4; 
len -= 4;

???

Referencia: http://murmurhash.googlepages.com/

Lo siento por mi Inglés y mi estupidez. Cheers

Fuente

2009-06-29 Anonymous

¿Has mirado en Wikipedia? http://en.wikipedia.org/wiki/MurmurHash – merkuro

+12

@merkuro ¿Has * mirado * el artículo de [Wikipedia] (http://en.wikipedia.org/wiki/MurmurHash)? –

El código está disponible here. m y r son constantes utilizadas por el algoritmo. k * = m significa tomar la variable k y multiplicarla por m. k^= k >> r significa tomar k y desplazar a la derecha los bits r lugares (por ejemplo, si r es 2 110101 se convertiría en 001101) y luego XOR con k.

Espero que te brinde lo suficiente para trabajar en el resto.

Saludos

Fuente

2009-06-29 08:13:19

la mejor explicación del soplo algoritmo está en el Murmur Hash Wikipedia page:

 
Murmur3_32(key, len, seed) 
    //Note: In this version, all integer arithmetic is performed 
    //with unsigned 32 bit integers. In the case of overflow, 
    //the result is constrained by the application 
    //of modulo 2³² arithmetic. 

    c1 ← 0xcc9e2d51 
    c2 ← 0x1b873593 
    r1 ← 15 
    r2 ← 13 
    m ← 5 
    n ← 0xe6546b64 

    hash ← seed 

    for each fourByteChunk of key 
     k ← fourByteChunk 

     k ← k × c1 
     k ← (k ROL r1) 
     k ← k × c2 

     hash ← hash XOR k 
     hash ← (hash ROL r2) 
     hash ← hash × m + n 

    with any remainingBytesInKey 
     remainingBytes ← SwapEndianOrderOf(remainingBytesInKey) 
     // Note: Endian swapping is only necessary on big-endian machines. 

     remainingBytes ← remainingBytes × c1 
     remainingBytes ← (remainingBytes ROL r1) 
     remainingBytes ← remainingBytes × c2 

     hash ← hash XOR remainingBytes 

    hash ← hash XOR len 

    hash ← hash XOR (hash SHR 16) 
    hash ← hash × 0x85ebca6b 
    hash ← hash XOR (hash SRH 13) 
    hash ← hash × 0xc2b2ae35 
    hash ← hash XOR (hash SHR 16)

Y mi propia:

Fuente

2015-08-12 03:17:17

Ese es el código. Cierto pseudo código bastante legible, pero sigo sin entender la '' explicación ''. Obtengo lo que están haciendo los pasos, podría escribirlo en varios idiomas, pero no entiendo qué aporta cada paso al hash, como: matemáticamente y esas cosas. (Todavía estoy buscando una buena explicación, no estoy atacando esta respuesta ni nada). – Noein

@Noein ¿Qué hay de la hermosa imagen que acabo de agregar? –

Bueno, no dice nada sobre las propiedades matemáticas de una manera que yo puedo entender ... Pero probablemente estoy por delante de mí mismo, el diagrama me ayudó a escribir una versión sin mirar una implementación real, más que el pseudo-código, así que gracias;) – Noein

Por favor explique murmur hash?

Respuesta

Cuestiones relacionadas