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

MurmurHash3 là một hàm băm không mã hóa được Austin Appleby thiết kế vào năm 2008. Nó được sử dụng rộng rãi cho mục đích băm chung do tốc độ, tính đơn giản và 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 loại bỏ trùng lặp dữ liệu.

Biến thể được trình bày trên trang này là biến thể 3C, được tối ưu hóa cho hệ thống 32 bit, giống như biến thể 3A. Tuy nhiên, không giống như biến thể 3A, nó tạo ra mã băm 128 bit (16 byte), thường được biểu diễn dưới dạng số thập lục phân 32 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.

Về thuật toán băm MurmurHash3C

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 loại suy mà những người không phải nhà toán học như tôi có thể hiểu được. Nếu bạn thích một lời giải thích toán học chính xác về mặt khoa học, tôi chắc rằng bạn có thể tìm thấy ở nơi khác ;-)

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

MurmurHash3 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ỏ chúng thành một "dấu vân tay" nhỏ, cố định hoặc giá trị băm. 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ộ.

Một phép so sánh khác giống như 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 nướng nhỏ (băm). Đây sẽ là một quá trình gồm ba bước:

Bước 1: Cắt thành từng mảnh (Phá vỡ dữ liệu)

• Đầu tiên, MurmurHash3 cắt 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 ô vuông bằng nhau.

Bước 2: Trộn thật đều (Trộn các khối)

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

Bước 3: Kiểm tra hương vị cuối cùng (Hoàn thiện)

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