Giới thiệu MurMur hash
algorithm
30
White

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

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Hoàng Minh Trung

21 bài viết.
54 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
18 15
(Ảnh) Mục đích của bài viết là hướng dẫn cơ bản nhất cho những ai chưa biết về docker, môi trường thực hiện là mac OS. Chuẩn bị Cài đặt virtua...
Hoàng Minh Trung viết hơn 2 năm trước
18 15
White
17 1
Bài viết dịch từ http://arslan.io/tenusefultechniquesingo Sử dụng một GOPATH duy nhất Sử dụng đồng thời nhiều GOPATH sẽ không giúp cho hệ thống ...
Hoàng Minh Trung viết hơn 1 năm trước
17 1
White
13 0
Bài viết dịch từ https://github.com/luciotato/golangnotes/blob/master/OOP.md Mục đích bài viết Học golang dễ dàng hơn với những kiến thức bạn đ...
Hoàng Minh Trung viết hơn 1 năm trước
13 0
Bài viết liên quan
White
41 7
Là một người thường xuyên đọc Quora, có một điểm cá nhân tôi thấy rất ấn tượng ở quora chính là khả năng autocomplete với tốc độ ánh sáng. (Ảnh) ...
huydx viết 2 tháng trước
41 7
White
2 0
What is competitive programming? Sites like CodeForces, TopCoder, HackerRank, CodeChef,... ACMICPC, Olympiad in Informatics (for high school stude...
Nguyễn Lê Vũ Long viết 7 tháng trước
2 0
White
71 34
Bài viết thuộc chủ đề nghiên cứu trong nhóm hardcore của Cộng đồng Ruby Việt Nam Đọc manga trên mobile là một nhu cầu rất lớn, nhưng hiện nay chư...
Huy Trần viết hơn 1 năm trước
71 34
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
21 bài viết.
54 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!