- Băm đa lựa chọn (Multiple choice hashing) được đặt tên vì nó sử dụng nhiều hàm băm (hash functions).
- Ở cấp độ cao, khi có nhiều hàm băm, mỗi mục được ánh xạ đến nhiều bucket (ngăn) và do đó người thiết kế thuật toán (Algorithm designer) có tự do chọn mục sẽ nằm ở bucket nào trong số đó.
- Điều này cho phép các thuật toán đạt được phân bổ (allocations) cân bằng hơn nhiều so với dùng một hàm băm đơn.
- Chúng ta sẽ trình bày các ý tưởng thuật toán chính và công cụ toán học chính dùng để chứng minh ranh giới trên phân bổ mà các thuật toán này tạo ra.
- Chúng ta sẽ thấy phân tích đủ mạnh để chịu đựng các biến thể trong mô hình cơ bản, điều mà theo quan điểm của chúng ta giải thích hiệu quả của các thuật toán này trong ứng dụng thực tế.
Thuật toán Multiple Choice Hashing được giải thích bằng ví dụ mô hình ball-into-bins (quả bóng vào thùng).
- Một khung phổ biến để suy luận về quá trình cân bằng tải (load balancing) là mô hình 'quả bóng' (balls) và 'thùng' (bins) nơi nhu cầu (khóa, tiến trình, file...) được biểu diễn bởi 'quả bóng' và nguồn cung tài nguyên (ô bảng băm, server, đơn vị lưu trữ...) được biểu diễn bởi 'thùng'.
- Trong cài đặt này, m quả bóng được ném vào n thùng tuần tự bằng một quy tắc phân bổ (allocation rule).
- Mục tiêu là hiểu phân bổ quả bóng vào thùng sau khi quá trình hoàn tất, thường chặn tải (load = số quả bóng) trong thùng tải nhiều nhất.
- Theo mô hình này, gán quả bóng vào thùng bằng cách áp dụng một hoặc nhiều hàm băm.
- Các hàm băm này chịu trách nhiệm ánh xạ id duy nhất của quả bóng (thường ngầm hiểu trong mô hình) đến tập thùng, thường đánh số 1...n.
- Dùng hàm băm ánh xạ thùng đến quả bóng, thay vì đơn giản rút thùng ngẫu nhiên, hữu ích trong trường hợp phổ biến sau này cần khôi phục vị trí quả bóng từ id của nó.