- मल्टीपल चॉइस हैशिंग (Multiple Choice Hashing) का नाम इसलिए पड़ा क्योंकि यह कई हैश फंक्शन्स (Multiple Hash Functions) के कार्यान्वयन को नियोजित करता है।
- उच्च स्तर पर, जब कई हैश फंक्शन्स होते हैं तो प्रत्येक आइटम कई बकेट्स (Buckets) में मैप होता है और इसलिए एल्गोरिदम डिज़ाइनर को उनमें से चयन करने की स्वतंत्रता होती है कि आइटम उनमें से किसमें रहेगा।
- यह पता चलता है कि यह स्वतंत्रता उन एल्गोरिदम के लिए अनुमति देती है जो सिंगल हैश फंक्शन लागू करके प्राप्त आवंटन की तुलना में बहुत अधिक संतुलित आवंटन (Balanced Allocations) प्राप्त करते हैं।
- हम मुख्य एल्गोरिदमिक विचारों और मुख्य गणितीय उपकरणों को प्रस्तुत करेंगे जो इन एल्गोरिदम द्वारा उत्पादित आवंटन पर बाउंड साबित करने के लिए लागू होते हैं।
- हम देखेंगे कि विश्लेषण बेसिक मॉडल में विविधताओं का सामना करने के लिए पर्याप्त शक्तिशाली है जो हमारे विचार में व्यावहारिक अनुप्रयोगों में इन एल्गोरिदम की प्रभावशीलता की व्याख्या करता है।
मल्टीपल चॉइस हैशिंग का एल्गोरिदम बॉल्स-इन्टू-बिन्स मॉडल (Balls-into-bins Model) के उदाहरण का हवाला देकर समझाया गया है
- लोड बैलेंसिंग प्रक्रियाओं के बारे में तर्क के लिए एक सामान्य फ्रेमवर्क 'बॉल्स' और 'बिन्स' का है जहां मांग (कीज़, प्रोसेस, फाइल्स आदि) 'बॉल्स' द्वारा दर्शाई जाती है और संसाधनों की आपूर्ति (टेबल स्लॉट्स, सर्वर, स्टोरेज यूनिट्स आदि) 'बिन्स' द्वारा दर्शाई जाती है।
- इस सेटिंग में कुछ आवंटन नियम (Allocation Rule) लागू करके क्रमिक रूप से (Sequentially) n बिन्स में m संख्या में बॉल्स फेंके जाते हैं।
- लक्ष्य प्रक्रिया पूरी होने के बाद बॉल्स के बिन्स में आवंटन को समझना है, आमतौर पर अधिकतम लोडेड बिन में लोड (=बॉल्स की संख्या) को बांधना।
- इस मॉडल के अनुसार बिन्स को बॉल्स का असाइनमेंट एक या अधिक हैश फंक्शन्स लागू करके किया जाता है।
- ये हैश फंक्शन्स बॉल के यूनिक आईडी (आमतौर पर मॉडल में निहित) को बिन्स के सेट (आमतौर पर 1...n नंबर) पर मैप करने के लिए जिम्मेदार हैं।
- बिन को बॉल पर मैप करने के लिए हैश फंक्शन लागू करना, केवल रैंडमली बिन खींचने के बजाय, सामान्य मामले में उपयोगी है जहां बाद में किसी समय, बॉल की लोकेशन को उसके आईडी से रिकवर करने की आवश्यकता होती है।
