Máy tính mã băm Fowler-Noll-Vo FNV1-32

Hàm băm 32 bit FNV-1 là một phần của họ hàm băm Fowler–Noll–Vo (FNV), được thiết kế để băm nhanh trong khi vẫn duy trì sự phân bố tốt các giá trị băm. Nó thường được sử dụng trong các ứng dụng như bảng băm, kiểm tra tổng và tra cứu dữ liệu. 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 32 bit Fowler-Noll-Vo FNV-1

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 thích một lời giải thích chính xác về mặt khoa học, mang tính toán học cao, chắc chắn bạn có thể tìm thấy nó ở nơi khác ;-)

Trước tiên, hãy hình dung thuật toán FNV-1 như một công thức pha chế một loại sinh tố đặc biệt. Mỗi thành phần bạn thêm vào (như trái cây, sữa hoặc mật ong) đại diện cho một mẩu dữ liệu - chẳng hạn như chữ cái, số hoặc thậm chí là toàn bộ một tập tin.

Mục tiêu là trộn các nguyên liệu này theo một cách rất cụ thể sao cho ngay cả một thay đổi nhỏ nhất trong công thức (như thêm một quả việt quất) cũng làm cho sinh tố có hương vị hoàn toàn khác. Đó là cách các hàm băm hoạt động - chúng tạo ra một "hương vị" (hoặc giá trị băm) độc đáo cho mỗi tập hợp nguyên liệu (hoặc dữ liệu đầu vào) duy nhất.

Thuật toán FNV-1 thực hiện điều này thông qua một quy trình nhiều bước:

Bước 1: Bắt đầu với một cơ sở (Cơ sở bù trừ)

Hãy tưởng tượng như việc bạn đổ một loại bột sinh tố đặc biệt vào máy xay sinh tố. Loại bột này luôn giữ nguyên, bất kể bạn thêm nguyên liệu gì vào. Trong FNV-1, điều này được gọi là "cơ sở bù trừ" - chỉ là một con số khởi đầu khá hoa mỹ.

Bước 2: Thêm từng nguyên liệu một (Xử lý dữ liệu)

Bây giờ bạn bắt đầu thêm từng nguyên liệu một - ví dụ như một quả dâu tây, rồi một quả chuối, rồi một ít mật ong. Mỗi nguyên liệu này đại diện cho một byte dữ liệu.

Bước 3: Kết hợp với hệ số nhân bí mật (FNV Prime)

Sau khi cho từng nguyên liệu vào, bạn nhấn nút xay, nhưng điểm đặc biệt ở đây là: máy xay sẽ nhân tất cả các nguyên liệu với một "con số kỳ diệu" bí mật gọi là FNV prime. Điều này giúp trộn đều các nguyên liệu hơn.

Bước 4: Thêm chút phép thuật (Phép toán XOR)

Trước khi thêm nguyên liệu tiếp theo, bạn rắc thêm một chút "bột thần kỳ" (đây là phép toán XOR). Nó giống như việc đảo ngược hương vị theo những cách bất ngờ, đảm bảo ngay cả những thay đổi nhỏ cũng tạo ra sự khác biệt lớn.

Bước 5: Lặp lại cho đến khi hoàn tất

Bạn tiếp tục xay và rắc thêm gia vị sau mỗi nguyên liệu mới cho đến khi xay xong tất cả mọi thứ.

Bước 6: Kết quả cuối cùng của sinh tố (Giá trị băm)

Khi làm xong, bạn đổ sinh tố ra. Hương vị cuối cùng (giá trị băm) là duy nhất đối với sự kết hợp chính xác của các nguyên liệu đó. Nếu bạn thêm dù chỉ một quả việt quất nữa, hương vị sẽ hoàn toàn khác.

Phiên bản được trình bày ở đây là phiên bản FNV-1 32 bit gốc. Ngoài ra còn có phiên bản FNV-1a 32 bit được cải tiến: [Liên kết]

Đọ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 CRC-32C
• Máy tính mã băm MurmurHash3A
• Máy tính mã băm CRC-32