Vui lòng giải thích hàm băm không?

Question

Tôi vừa phát hiện ra hàm băm nhỏ, có vẻ là khả năng chống va chạm khá nhanh và nổi tiếng nhất. Tôi đã cố gắng tìm hiểu thêm về thuật toán hoặc triển khai trong mã nguồn đầy đủ, nhưng tôi gặp khó khăn trong việc hiểu nó. Có thể ai đó ở đây giải thích thuật toán được sử dụng, hoặc thực hiện nó trong mã nguồn đầy đủ, tốt nhất là trong C. Tôi đọc mã nguồn C từ trang web tác giả nhưng không có ý tưởng, như: hạt giống, h, k, m là gì? điều này có nghĩa là:

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

h *= m; 
h ^= k; 

data += 4; 
len -= 4; 

???

Tham chiếu: http://murmurhash.googlepages.com/

Xin lỗi vì tiếng Anh và sự ngu ngốc của tôi. Chúc mừng

Answer 1

Mã có sẵn here. m và r là hằng số được sử dụng bởi thuật toán. k * = m có nghĩa là lấy biến k và bội số bằng m. k^= k >> r có nghĩa là lấy k và dịch phải các vị trí bit r (ví dụ: nếu r là 2 110101 sẽ trở thành 001101) và sau đó XOR nó bằng k.

Hy vọng cung cấp cho bạn đủ để làm việc thông qua phần còn lại.

Trân

Answer 2

Lời giải thích tốt nhất của Murmur thuật toán là trên 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 232 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) 

Và riêng tôi: