- มีการตั้งชื่อการแฮชแบบหลายตัวเลือก เนื่องจากมีการใช้ฟังก์ชันแฮชหลายแบบ
- ในระดับสูง เมื่อมีฟังก์ชันแฮชหลายรายการ แต่ละรายการจะจับคู่กับหลายบัคเก็ต ดังนั้นผู้ออกแบบอัลกอริทึมจึงมีอิสระในการเลือกว่ารายการใดจะอยู่ที่ใด
- ปรากฎว่าเสรีภาพนี้อนุญาตให้ใช้อัลกอริธึมที่ได้รับการจัดสรรที่มีความสมดุลมากกว่าที่ได้รับจากการใช้ฟังก์ชันแฮชเดียว
- เราจะนำเสนอแนวคิดเกี่ยวกับอัลกอริทึมหลักและเครื่องมือทางคณิตศาสตร์หลักที่นำมาใช้เพื่อพิสูจน์ขอบเขตของการจัดสรรที่อัลกอริทึมเหล่านี้สร้างขึ้น
- เราจะเห็นว่าการวิเคราะห์มีประสิทธิภาพเพียงพอที่จะทนต่อการเปลี่ยนแปลงในรูปแบบพื้นฐาน ซึ่งในมุมมองของเราได้อธิบายถึงประสิทธิภาพของอัลกอริทึมเหล่านี้ในการใช้งานจริง
Algorithm of Multiple Choice Hashing อธิบายโดยยกตัวอย่างของแบบจำลองลูกลงถังขยะ
- กรอบงานทั่วไปสำหรับการให้เหตุผลเกี่ยวกับกระบวนการปรับสมดุลโหลดคือ 'ลูกบอล' และ 'ถังขยะ' โดยที่ความต้องการ (คีย์ กระบวนการ ไฟล์ ฯลฯ..) ถูกแสดงด้วย 'ลูกบอล' และการจัดหาทรัพยากร (ช่องตาราง เซิร์ฟเวอร์ หน่วยเก็บข้อมูล ฯลฯ..) จะแสดงด้วย "ถังขยะ"
- ในการตั้งค่านี้ m ไม่ ของลูกบอลถูกโยนลงใน n ถังขยะตามลำดับโดยใช้กฎการจัดสรรบางอย่าง
- เป้าหมายคือการทำความเข้าใจการจัดสรรลูกบอลลงในถังขยะหลังจากเสร็จสิ้นกระบวนการ โดยปกติแล้วจะจำกัดน้ำหนัก (=จำนวนลูกบอล) ในถังบรรจุสูงสุด
- ตามรูปแบบการกำหนดลูกบอลนี้ไปยังถังขยะโดยใช้ฟังก์ชันแฮชอย่างน้อยหนึ่งฟังก์ชัน
- ฟังก์ชันแฮชเหล่านี้มีหน้าที่ในการแมป id เฉพาะของลูกบอล (โดยทั่วไปจะระบุโดยนัยในแบบจำลอง) กับชุดของถังขยะ ซึ่งโดยทั่วไปแล้วจะมีหมายเลข 1...n.
- การใช้ฟังก์ชันแฮชเพื่อจับคู่ถังขยะกับลูกบอล แทนที่จะเพียงแค่สุ่มสุ่มถังขยะ มีประโยชน์ในกรณีทั่วไป ซึ่งในบางครั้ง ตำแหน่งของลูกบอลจะต้องถูกกู้คืนจากรหัสของมัน
