Multiple-Choice Hashing คืออะไร?
ใช้ Multiple Hash Functions → แต่ละ Item Map ไป Multiple Buckets
→ Algorithm Designer มี Freedom เลือกว่า Item จะอยู่ Bucket ไหน
→ ได้ Allocation ที่ Balanced กว่า Single Hash Function มาก
Balls-into-Bins Model (Framework มาตรฐาน)
- Balls = Demand (Keys, Processes, Files, etc.)
- Bins = Supply (Table Slots, Servers, Storage Units, etc.)
- m Balls → n Bins Sequentially ตาม Allocation Rule
- Goal: Bound Load (Balls in Max Loaded Bin) หลัง Process จบ
Hash Functions ใน Model นี้
- Hash Functions Map Ball's Unique ID → Set of Bins (Typically 1...n)
- ใช้ Hash Function แทน Random Draw เพื่อ: Recover Ball Location จาก ID ได้ภายหลัง
Key Algorithmic Ideas
- Multiple Choices (d Choices): แต่ละ Ball มี d Hash Functions → d Candidate Bins
- Greedy Placement: วางใน Bin ที่ Load น้อยสุดใน d Choices
- Power of Two Choices (d=2): Max Load = log log n / log 2 + O(1) (vs log n / log log n สำหรับ d=1)
- Always-Go-Left / Other Tie-breaking Rules
Mathematical Tools สำหรับ Analysis
- Witness Trees / Witness Sequences
- Layered Induction
- Differential Equations Method (Fluid Limits)
- Majorization Arguments
Robustness
Analysis ทนทานต่อ Variations ของ Basic Model → อธิบายได้ว่าทำไม Practical Applications ถึง Effective
สรุป
Multiple-Choice Hashing = Simple Idea (d Hash Functions + Greedy) → Exponential Improvement ใน Load Balancing
d=2 (Power of Two Choices) = Sweet Spot: Simple, Huge Gain
