Máy tính mã băm MurmurHash3A

MurmurHash3 là một hàm băm phi mật mã được thiết kế bởi Austin Appleby vào năm 2008. Nó được sử dụng rộng rãi cho việc băm đa năng nhờ tốc độ, sự đơn giản và các đặc tính phân phối tốt. Các hàm MurmurHash đặc biệt hiệu quả đối với các cấu trúc dữ liệu dựa trên băm như bảng băm, bộ lọc Bloom và hệ thống khử trùng lặp dữ liệu.

Biến thể được trình bày trên trang này là biến thể 3A, được tối ưu hóa cho hệ thống 32 bit. Nó tạo ra mã băm 32 bit (4 byte), thường được biểu diễn dưới dạng số thập lục phân 8 chữ số.

Tiết lộ đầy đủ: Tôi không viết phần triển khai cụ thể của hàm băm được sử dụng trên trang này. Đây là một hàm chuẩn đi kèm với ngôn ngữ lập trình PHP. Tôi chỉ tạo giao diện web để công khai ở đây cho thuận tiện.

Giới thiệu về thuật toán băm MurmurHash3A

Tôi không phải là nhà toán học, nhưng tôi sẽ cố gắng giải thích hàm băm này bằng một phép so sánh mà những người không chuyên về toán học như tôi có thể hiểu được. Nếu bạn muốn một lời giải thích chính xác về mặt khoa học, đầy đủ tính toán học, tôi chắc chắn bạn có thể tìm thấy nó ở nơi khác ;-)

Hãy tưởng tượng bạn có một hộp lớn đựng các viên gạch LEGO. Mỗi lần bạn sắp xếp chúng theo một cách cụ thể, bạn đều chụp ảnh. Cho dù cách sắp xếp có lớn hay nhiều màu sắc đến đâu, máy ảnh luôn cho bạn một bức ảnh nhỏ, có kích thước cố định. Bức ảnh đó thể hiện tác phẩm LEGO của bạn, nhưng ở dạng thu nhỏ.

MurmurHash3 cũng làm điều tương tự với dữ liệu. Nó lấy bất kỳ loại dữ liệu nào (văn bản, số, tệp) và thu nhỏ lại thành một "dấu vân tay" hoặc giá trị băm nhỏ, cố định. Dấu vân tay này giúp máy tính nhanh chóng xác định, sắp xếp và so sánh dữ liệu mà không cần phải xem toàn bộ dữ liệu.

Một ví dụ tương tự khác là việc nướng bánh và MurmurHash3 là công thức để biến chiếc bánh đó thành một chiếc bánh cupcake nhỏ (mã băm). Quá trình này gồm ba bước:

Bước 1: Chia nhỏ dữ liệu (Phân tích dữ liệu)

• Đầu tiên, MurmurHash3 chia dữ liệu của bạn thành các phần bằng nhau, giống như cắt bánh thành những hình vuông đều nhau.

Bước 2: Trộn thật kỹ (Trộn các miếng nguyên liệu)

• Mỗi phần đều trải qua một quá trình trộn phức tạp: Lật: Giống như lật bánh kếp, nó sắp xếp lại các phần tử. Khuấy: Thêm các thành phần ngẫu nhiên (các phép toán) để trộn lẫn mọi thứ. Ép: Ép dữ liệu lại với nhau để đảm bảo không có phần nào ban đầu nổi bật.

Bước 3: Thử nếm lần cuối (Hoàn thiện)

• Sau khi trộn tất cả các phần, MurmurHash3 thực hiện một lần khuấy cuối cùng để đảm bảo ngay cả một chút thay đổi nhỏ nhất trong dữ liệu gốc cũng sẽ hoàn toàn thay đổi hương vị (của hỗn hợp băm).

Đọc thêm

Nếu bạn thích bài viết này, bạn cũng có thể thích những gợi ý sau:

• Máy tính mã băm SHA-384
• Máy tính mã băm SHA-512/224
• Máy tính mã băm Tiger-128/3