Một Số Thảo Luận Về Hàm Băm Lua

TÌM HIỂU SÂU HƠN VỀ HÀM BĂM TRONG NGÔN NGỮ LUA
Trong thời gian gần đây, cộng đồng lập trình viên sử dụng ngôn ngữ Lua đã có nhiều cuộc thảo luận sôi nổi về thiết kế bảng băm (hash table). Những trao đổi này khiến tôi hiểu sâu sắc hơn về cơ chế hoạt động của cấu trúc dữ liệu này. Chẳng hạn như trong chuỗi thư trao đổi cách đây hai tuần, một thành viên đã đề xuất loại bỏ cơ chế danh sách liên kết trong bảng băm Lua và thay thế bằng cơ chế giải quyết va chạm sử dụng bước nhảy cố định. Để không làm bài viết quá dài dòng, tôi xin phép không đi sâu chi tiết ở đây - những ai quan tâm có thể tìm đọc chuỗi thư gốc.

Chủ đề nóng hổi nhất trong những ngày qua xoay quanh hàm băm của Lua. Vì chưa có đường dẫn cố định, tôi xin chia sẻ những hiểu biết cá nhân về vấn đề này. Những phân tích dưới đây có thể chưa hoàn toàn chính xác, hy vọng nhận được sự góp ý từ các chuyên gia:

1
2
3
4
5
6

unsigned int luaS_hash (const char *str, size_t l, unsigned int seed, size_t step) {
    unsigned int h = seed ^ cast_uint(l);
    for (; l >= step; l -= step)
        h ^= ((h<<5) + (h>>2) + cast_byte(str[l - 1]));
    return h;
}

Phân tích biểu thức (h<<5) + (h>>2) trong hàm trên, chúng ta có thể thấy nó tương đương với ((h<<7) + h) >> 2. Điểm khác biệt nằm ở chỗ cách xử lý hai bit cao nhất, biểu thức đầu tiên giữ lại hai bit này thay vì dịch chuyển hoàn toàn. Khi phân tích sâu hơn, (h<<7) + h chính là phép nhân h với 129, điều này khiến thuật toán này trở thành một biến thể của phương pháp băm được Donald Knuth trình bày trong cuốn “The Art of Computer Programming” tập 3 phiên bản 2, mục 6.4.

Tuy nhiên, con số 129 không phải số nguyên tố - yếu tố quan trọng trong thiết kế hàm băm. Tại sao số nguyên tố lại được ưu tiên? Câu trả lời nằm ở bản chất của hàm băm: giống như bộ tạo số giả ngẫu nhiên, chúng cần biến đổi dữ liệu đầu vào thành chuỗi giá trị ngẫu nhiên. Trong thực tế, số lượng bucket trong bảng băm thường nhỏ nên kết quả băm sẽ bị chia dư cho kích thước bucket. Khi dữ liệu mang tính ngẫu nhiên cao, khả năng xảy ra va chạm sẽ thấp hơn.

Trong các hàm băm dựa trên thuật toán LCG (Linear Congruential Generator), chu kỳ của chuỗi số tạo ra phụ thuộc vào việc chọn số nhân. Số nguyên tố lớn sẽ tạo chu kỳ dài hơn so với các số không nguyên tố có cùng độ lớn, bởi các số này có thể phân tích thành tích của các số nguyên tố nhỏ hơn. Việc sử dụng phép dịch bit và cộng thay phép nhân xuất phát từ giả định rằng phép nhân tốn nhiều tài nguyên hơn. Tuy nhiên, thực chất phép nhân chính là tổ hợp của nhiều phép dịch và cộng, nên việc tối ưu cần cân nhắc cẩn trọng giữa số lần dịch và hiệu năng.

Một đề xuất thú vị từ diễn đàn là thay thế biểu thức trên bằng (h<<4)-(h>>3), tương đương với phép tính (h*127)>>>3 đồng thời bảo toàn 3 bit cao nhất. Khác biệt chính nằm ở số nhân 127 - một số nguyên tố Mersenne (số có dạng 2ⁿ-1). Việc sử dụng số Mersenne cho phép biểu diễn qua một phép dịch và một phép trừ. Sự lựa chọn dịch 3 bit thay vì 2 bit bắt nguồn từ cách xử lý luồng dữ liệu theo chiều dài từ máy tính: khi dữ liệu được nạp theo từng “word”, việc dùng số lẻ như 3 sẽ phân bố tốt hơn so với số chẵn như 2.

Trong các hệ thống có phép nhân hiệu suất cao, có thể nên sử dụng trực tiếp phép nhân với số nhân được chọn kỹ lưỡng. Giáo sư Thomas Wang trong bài viết nổi tiếng “Integer Hash Function” đã phân tích chi tiết cách xây dựng hàm băm hiệu quả. Ông nhấn mạnh rằng một hàm băm tốt cần đảm bảo khả năng đảo ngược từng bước tính toán. Điều này đảm bảo ánh xạ 1-1 giữa đầu vào và đầu ra, giảm thiểu va chạm. Các phép toán có tính khả nghịch bao gồm: cộng/trừ, dịch trái, đảo bit, XOR. Phép nhân tuy phức tạp hơn nhưng bản chất cũng là tổ hợp của phép dịch và cộng.

Để đạt được tính “ngẫu nhiên nhị phân” (mỗi bit có 50% xác suất là 0 hoặc 1), quá trình tính toán băm cần khuếch tán sự thay đổi của từng bit đầu vào ra nhiều bit đầu ra. Trong các phép toán khả nghịch, dịch bit và XOR chủ yếu thay đổi vị trí hoặc đảo giá trị bit, trong khi phép cộng/trừ mới là yếu tố tạo ra sự biến đổi thực sự. Ví dụ: 0111 + 1 = 1000 khiến nhiều bit liên tiếp thay đổi giá trị. Sự kết hợp thông minh giữa các phép toán này chính là chìa khóa tạo ra hiệu ứng “trộn đều” mong muốn.

Xét về hiệu quả tính toán, phép nhân mang lại hiệu suất cao nhờ thực hiện nhiều phép dịch và cộng trong một bước. Số lần cộng tương ứng với số đoạn bit 1 liên tiếp trong biểu diễn nhị phân của số nhân. Từ góc nhìn này, các số nhân có dạng bit đan xen như 0101010101… sẽ tối ưu nhất. Với từ dữ liệu 32 bit, số nhân 16 bit như 0x5555 (tương đương 0b0101010101010101) lý tưởng về mặt phân bố bit, nhưng tiếc rằng đây là bội số của 5 nên không phải số nguyên tố. Một lựa chọn tốt hơn là 0xAAAB (0b1010101010101011) - số nguyên tố 43691. Thậm chí, mẫu bit “hai 1, một 0” như 0xB6DB (0b1011011011011011) cho ra số nguyên tố lớn hơn 46811.

Knuth cũng đã đề xuất số nhân 2654435761 cho từ 64 bit - con số này nằm gần điểm vàng (golden ratio) của 2³². Trong thực nghiệm, tôi đã thực hiện kiểm thử với hơn 30,000 từ tiếng Anh ngẫu nhiên để đánh giá hiệu suất tránh va chạm của các hàm băm. Kết quả cho thấy biểu thức (h<<4) - (h>>3) + x cho hiệu quả tốt nhất, trong khi phiên bản gốc `(h«5) + (h