Giới thiệu MurMur hash

algorithm

35

Hoàng Minh Trung viết ngày 23/02/2016

Tranh thủ rỗi note lại về cái thuật toán hash khá nổi tiếng gọi là MurMur (tên khá thú vị)
MurMur là một hàm hash non-crypto (tức là ai thích thì có thể giải mã được ).
Hàm hash này có rất nhiều ứng dụng, như là trong database để Partition (chia dữ liệu ra thành nhiều khu, mà sử dụng hash để phân biệt khu này khu kia)

Một hàm hash tốt thì phải có đặc điểm là Random Uniformly, dịch nôm na ra có nghĩa là ngẫu nhiên một cách "đều đặn".
Tức là giả sử bạn có 1 tỉ phần tử, muốn hash ra thành 3 khu, dùng chung một hàm hash, thì hàm này phải giúp cho sau khi phân xong, mỗi khu sẽ chứa "tầm tầm" 300 triệu phần tử.

Thuật toán này chỉ là một chuỗi các thao tác byte, mà gồm 2 thao tác chính là nhân (MU-multiply) và lật (R-rotate) (chính vì vậy mà nó có tên là murmur). Nó có vài biến thể nhưng biến thể được dùng nhiều nhất gọi là MurMur3, có thể out ra kết quả là chuỗi 32 bit hoặc là 128 bit.

Cụ thể thì có đoạn code sau mình cóp nguyên từ ... wikipedia

#define ROT32(x, y) ((x << y) | (x >> (32 - y))) // avoid effort
uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed) {
    static const uint32_t c1 = 0xcc9e2d51;
    static const uint32_t c2 = 0x1b873593;
    static const uint32_t r1 = 15;
    static const uint32_t r2 = 13;
    static const uint32_t m = 5;
    static const uint32_t n = 0xe6546b64;

    uint32_t hash = seed;

    const int nblocks = len / 4;
    const uint32_t *blocks = (const uint32_t *) key;
    int i;
    uint32_t k;
    for (i = 0; i < nblocks; i++) {
        k = blocks[i];
        k *= c1;
        k = ROT32(k, r1);
        k *= c2;

        hash ^= k;
        hash = ROT32(hash, r2) * m + n;
    }

    const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
    uint32_t k1 = 0;

    switch (len & 3) {
    case 3:
        k1 ^= tail[2] << 16;
    case 2:
        k1 ^= tail[1] << 8;
    case 1:
        k1 ^= tail[0];

        k1 *= c1;
        k1 = ROT32(k1, r1);
        k1 *= c2;
        hash ^= k1;
    }

    hash ^= len;
    hash ^= (hash >> 16);
    hash *= 0x85ebca6b;
    hash ^= (hash >> 13);
    hash *= 0xc2b2ae35;
    hash ^= (hash >> 16);

    return hash;
}

Tham khảo

• http://research.neustar.biz/2012/02/02/choosing-a-good-hash-function-part-1/
• http://research.neustar.biz/2012/02/02/choosing-a-good-hash-function-part-2/
• http://research.neustar.biz/2012/02/02/choosing-a-good-hash-function-part-3/