Xử Lý Bảng Trong Lua
Lua sở hữu một cơ chế xử lý bảng (table) vô cùng tinh tế và hiệu quả, đây chính là yếu tố đóng vai trò quan trọng trong hiệu suất tổng thể của ngôn ngữ này. Bảng trong Lua không chỉ đơn thuần là một cấu trúc dữ liệu mà còn kiêm nhiệm nhiều vai trò như mảng động, từ điển ánh xạ, thậm chí là cơ sở cho các kiểu dữ liệu trừu tượng khác. Để tối ưu hóa hiệu năng, Lua đã thiết kế bảng theo một kiến trúc lai giữa hai thành phần chính: phần mảng (array part) và phần băm (hash part).
Với thiết kế thông minh này, các khóa số nguyên liên tục (như 1, 2, 3,…) sẽ được ưu tiên lưu trữ trong phần mảng - nơi cho phép truy cập với tốc độ O(1) tương đương như mảng thuần túy trong ngôn ngữ C. Tuy nhiên, khi gặp các khóa số nguyên phân tán (ví dụ như 1, 1000, 1000000), hệ thống sẽ tự động chuyển những khóa có giá trị lớn sang phần băm để tránh lãng phí không gian. Tiêu chí phân chia giữa hai phần này dựa trên nguyên tắc: phần mảng phải duy trì hiệu suất sử dụng tối thiểu 50%. Đặc biệt, các khóa là số âm hoặc số 0 sẽ luôn được xử lý trong phần băm.
Đối với phần băm, Lua áp dụng cơ chế băm đóng (closed hashing), nơi mọi giá trị đều được lưu trực tiếp trong bảng chính. Các khóa dạng chuỗi và số thực sẽ được xử lý riêng biệt bằng các hàm băm chuyên dụng, nhưng kết quả băm của chúng sẽ cùng tồn tại trong một không gian số học thống nhất. Khi xảy ra va chạm (collision), thay vì tạo vùng nhớ phụ, Lua sẽ tận dụng các ô trống còn lại trong bảng để lưu trữ các khóa liên quan. Mỗi ô dữ liệu trong phần băm đều chứa một con trỏ “next” để liên kết các khóa va chạm, tạo thành cơ chế xử lý va chạm lai giữa kỹ thuật mở rộng bảng và danh sách liên kết.
Quy trình mở rộng bảng (rehashing) được kích hoạt khi bảng gần đầy, lúc này toàn bộ dữ liệu sẽ được phân bố lại theo kích thước mới lớn hơn, giúp giảm thiểu đáng kể số lần va chạm. Trong quá trình chèn dữ liệu mới, Lua sử dụng một con trỏ đặc biệt để quét tuần tự từ đầu đến cuối bảng nhằm tìm vị trí trống phù hợp, đảm bảo hiệu suất tìm kiếm ổn định ngay cả khi bảng bị đầy.
Giải pháp này mang lại nhiều ưu điểm vượt trội:
- Tối ưu hóa tốc độ truy cập cho cả hai trường hợp mảng và từ điển
- Giảm thiểu lãng phí bộ nhớ thông qua cơ chế phân chia động giữa phần mảng và phần băm
- Cân bằng giữa tốc độ và không gian thông qua thuật toán rehashing thông minh
Trước đây, tôi cũng từng nghiên cứu một phương pháp triển khai bảng ánh xạ kết hợp giữa cấu trúc cây và vector, nhằm tạo ra sự cân bằng giữa hiệu suất truy cập và khả năng mở rộng. Nghiên cứu này đã được chia sẻ chi tiết trong một bài viết trước đây với tiêu đề “Cấu trúc cây-bảng kết hợp: Giải pháp trung hòa giữa vector, map và list”.