- Hàm băm nhiều lựa chọn được đặt tên vì nó sử dụng việc triển khai nhiều hàm băm.
- Ở cấp độ cao, khi có nhiều hàm băm, mỗi mục sẽ được ánh xạ tới nhiều nhóm và do đó Công cụ thiết kế thuật toán có quyền tự do chọn trong số đó mà mục sẽ nằm trong đó.
- Nó chỉ ra rằng sự tự do này cho phép các Thuật toán có được các phân bổ cân bằng hơn nhiều so với sau đó được tận dụng bằng cách triển khai một hàm băm duy nhất.
- Chúng tôi sẽ trình bày các ý tưởng chính của Thuật toán và các công cụ toán học chính được triển khai để chứng minh giới hạn phân bổ mà các Thuật toán này tạo ra.
- Chúng tôi sẽ thấy rằng phân tích đủ mạnh để chống lại các biến thể trong mô hình cơ bản, theo quan điểm của chúng tôi giải thích tính hiệu quả của các Thuật toán này trong các ứng dụng thực tế.
Thuật toán băm nhiều lựa chọn được giải thích bằng cách trích dẫn ví dụ về mô hình bi vào thùng
- Một khuôn khổ chung để lý luận về các quy trình cân bằng tải là 'quả bóng' và 'thùng' trong đó nhu cầu (khóa, quy trình, tệp, v.v.) được thể hiện bằng 'quả bóng' và nguồn cung cấp (vị trí bảng, máy chủ, đơn vị lưu trữ, v.v.) được biểu thị bằng 'thùng'.
- Trong cài đặt này, tôi không. các quả bóng được ném vào n thùng một cách tuần tự bằng cách thực hiện một số quy tắc phân bổ.
- Mục tiêu là để hiểu việc phân bổ các quả bóng vào các thùng sau khi hoàn thành quy trình, thường là giới hạn tải (=số lượng quả bóng) trong thùng được tải tối đa.
- Theo mô hình này, việc gán bóng được thực hiện cho các 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 là ẩn trong mô hình) với tập hợp các thùng, thường được đánh số 1 ... n.
- Việc triển khai một hàm băm để ánh xạ một thùng đến một quả bóng, thay vì chỉ vẽ một thùng một cách ngẫu nhiên, rất hữu ích trong trường hợp phổ biến là tại một số thời điểm tiếp theo, vị trí của một quả bóng cần được khôi phục từ id của nó.