हॉप्सकॉच हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[Image:hopscotch-wiki-example.gif|thumb|upright=2.5| हॉप्सकॉच हैशिंग। यहाँ, H 4 है। ग्रे प्रविष्टियाँ व्याप्त हैं। भाग (ए) में, आइटम x को 6 के हैश मान के साथ जोड़ा गया है। एक रैखिक जांच से पता चलता है कि प्रविष्टि 13 खाली है। चूँकि 13, 6 से 4 से अधिक प्रविष्टियाँ दूर है, एल्गोरिथ्म 13 के साथ स्वैप करने के लिए पहले वाली प्रविष्टि की तलाश करता है। देखने के लिए पहली जगह प्रविष्टि 10 पर पहले की H−1 = 3 प्रविष्टियाँ हैं। उस प्रविष्टि की हॉप जानकारी बिट-मैप इंगित करती है वह d, प्रविष्टि 11 पर आइटम, 13 पर विस्थापित किया जा सकता है। d को विस्थापित करने के बाद, प्रविष्टि 11 अभी भी प्रविष्टि 6 से बहुत दूर है, इसलिए एल्गोरिथ्म प्रविष्टि 8 की जांच करता है। हॉप सूचना बिट-मैप इंगित करता है कि प्रविष्टि 9 पर आइटम c हो सकता है अंत में, a को प्रविष्टि 9 में ले जाया जाता है। भाग (बी) x जोड़ने से ठीक पहले टेबल स्थिति दिखाता है।]]हॉपस्कॉच हैशिंग [[कंप्यूटर प्रोग्रामिंग]] में ओपन एड्रेसिंग का उपयोग करके टेबल में [[हैश फंकशन]] के मूल्यों के हैश टकराव को हल करने की एक योजना है। यह [[समवर्ती हैश तालिका|समवर्ती हैश टेबल]] को कार्यान्वित करने के लिए भी उपयुक्त है। होपस्कॉच हैशिंग | [[Image:hopscotch-wiki-example.gif|thumb|upright=2.5| हॉप्सकॉच हैशिंग। यहाँ, H 4 है। ग्रे प्रविष्टियाँ व्याप्त हैं। भाग (ए) में, आइटम x को 6 के हैश मान के साथ जोड़ा गया है। एक रैखिक जांच से पता चलता है कि प्रविष्टि 13 खाली है। चूँकि 13, 6 से 4 से अधिक प्रविष्टियाँ दूर है, एल्गोरिथ्म 13 के साथ स्वैप करने के लिए पहले वाली प्रविष्टि की तलाश करता है। देखने के लिए पहली जगह प्रविष्टि 10 पर पहले की H−1 = 3 प्रविष्टियाँ हैं। उस प्रविष्टि की हॉप जानकारी बिट-मैप इंगित करती है वह d, प्रविष्टि 11 पर आइटम, 13 पर विस्थापित किया जा सकता है। d को विस्थापित करने के बाद, प्रविष्टि 11 अभी भी प्रविष्टि 6 से बहुत दूर है, इसलिए एल्गोरिथ्म प्रविष्टि 8 की जांच करता है। हॉप सूचना बिट-मैप इंगित करता है कि प्रविष्टि 9 पर आइटम c हो सकता है अंत में, a को प्रविष्टि 9 में ले जाया जाता है। भाग (बी) x जोड़ने से ठीक पहले टेबल स्थिति दिखाता है।]]हॉपस्कॉच हैशिंग [[कंप्यूटर प्रोग्रामिंग]] में ओपन एड्रेसिंग का उपयोग करके टेबल में [[हैश फंकशन]] के मूल्यों के हैश टकराव को हल करने की एक योजना है। यह [[समवर्ती हैश तालिका|समवर्ती हैश टेबल]] को कार्यान्वित करने के लिए भी उपयुक्त है। होपस्कॉच हैशिंग का प्रारम्भ 2008 में [[मौरिस हेर्लिही]], [[नीर शवित]] और मोरन तज़ाफिर द्वारा की गई थी।<ref>{{cite conference | ||
|last1=Herlihy |first1=Maurice | |last1=Herlihy |first1=Maurice | ||
|last2=Shavit |first2=Nir | |last2=Shavit |first2=Nir | ||
| Line 12: | Line 12: | ||
एल्गोरिथ्म ''n'' बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका ''प्रतिवेश'' ''H'' लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही [[कैश लाइन]] के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(''n'') आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है। | एल्गोरिथ्म ''n'' बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका ''प्रतिवेश'' ''H'' लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही [[कैश लाइन]] के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(''n'') आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है। | ||
हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली ''H−1'' प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, ''H'' 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश | हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली ''H−1'' प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, ''H'' 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश "आभासी" बकेट है जिसका निश्चित आकार होता है और निम्नलिखित ''H−1'' बकेट के साथ ओवरलैप होता है। सर्च को तेज़ करने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में "हॉप-सूचना" शब्द, एक ''H''-बिट बिटमैप सम्मिलित होता है जो इंगित करता है कि अगली ''H''−1 प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, शब्द को देखकर यह देखने के लिए कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करके एक आइटम को तुरंत पाया जा सकता है (अधिकांश आधुनिक प्रोसेसर विशेष बिट मैनिपुलेशन ऑपरेशन का समर्थन करते हैं जो "हॉप-सूचना" बिटमैप में लुकअप को बहुत तेज़ बनाते हैं)। | ||
यहां बकेट ''i'' में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है: | यहां बकेट ''i'' में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है: | ||
# यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो टेबल भरी हुई है; हैश टेबल का विस्तार करें और पुनः प्रयास करें। | # यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो टेबल भरी हुई है; हैश टेबल का विस्तार करें और पुनः प्रयास करें। | ||
# प्रविष्टि ''i'' से | # प्रविष्टि ''i'' से प्रारम्भ करते हुए, सूचकांक ''j'' पर एक खाली प्रविष्टि खोजने के लिए एक रैखिक जांच का उपयोग करें। (यदि कोई खाली स्लॉट उपस्थित नहीं है, तो टेबल भरी हुई है।) | ||
# जबकि ''(j−i) mod n ≥ H'', खाली स्लॉट को ''i'' की ओर निम्नानुसार ले जाएं: | # जबकि ''(j−i) mod n ≥ H'', खाली स्लॉट को ''i'' की ओर निम्नानुसार ले जाएं: | ||
## किसी आइटम ''y'' के लिए j से पहले ''H''−1 स्लॉट खोजें, जिसका हैश मान ''k, j'' के ''H''−1 के भीतर है, अर्थात ''(j−k)'' mod ''n < H'' (यह हॉप-सूचना शब्दों का उपयोग करके किया जा सकता है।) | ## किसी आइटम ''y'' के लिए j से पहले ''H''−1 स्लॉट खोजें, जिसका हैश मान ''k, j'' के ''H''−1 के भीतर है, अर्थात ''(j−k)'' mod ''n < H'' (यह हॉप-सूचना शब्दों का उपयोग करके किया जा सकता है।) | ||
##यदि ऐसी कोई वस्तु y सीमा के भीतर | ##यदि ऐसी कोई वस्तु y सीमा के भीतर उपस्थित नहीं है, तो टेबल भरी हुई है। | ||
## ''y'' को ''j'' पर ले जाएं, ''i'' के करीब एक नया खाली स्लॉट बनाएं। | ## ''y'' को ''j'' पर ले जाएं, ''i'' के करीब एक नया खाली स्लॉट बनाएं। | ||
## ''j'' को ''y'' द्वारा खाली किए गए खाली स्लॉट पर सेट करें और दोहराएं। | ## ''j'' को ''y'' द्वारा खाली किए गए खाली स्लॉट पर सेट करें और दोहराएं। | ||
# ''x'' को स्लॉट ''j'' में स्टोर करें और वापस लौटें। | # ''x'' को स्लॉट ''j'' में स्टोर करें और वापस लौटें। | ||
विचार यह है कि हॉपस्कॉच हैशिंग "खाली स्लॉट को वांछित | विचार यह है कि हॉपस्कॉच हैशिंग "खाली स्लॉट को वांछित बकेट की ओर ले जाता है"। यह इसे रैखिक जांच से अलग करता है जो उस खाली स्लॉट को छोड़ देता है जहां यह पाया गया था, संभवतः मूल बकेट से बहुत दूर, या कोयल हैशिंग से, जो मुफ्त बकेट बनाने के लिए, वांछित बकेट में से किसी एक वस्तु को बाहर ले जाता है लक्ष्य सरणियाँ, और उसके बाद ही विस्थापित वस्तु को नई जगह खोजने की कोशिश करता है। | ||
किसी आइटम को तालिका से हटाने के लिए, व्यक्ति बस उसे तालिका प्रविष्टि से हटा देता है। यदि पड़ोस की बकेट कैश संरेखित हैं, तो कोई | किसी आइटम को तालिका से हटाने के लिए, व्यक्ति बस उसे तालिका प्रविष्टि से हटा देता है। यदि पड़ोस की बकेट कैश संरेखित हैं, तो कोई पुनर्गठन ऑपरेशन लागू कर सकता है जिसमें संरेखण में सुधार करने के लिए आइटम को अब खाली स्थान पर ले जाया जाता है। | ||
हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट ढूंढने के लिए रैखिक जांच का उपयोग करने के कारण होता है, न कि मूल रैखिक जांच हैश तालिका एल्गोरिदम के अनुसार प्रत्येक लुकअप के लिए। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल फ़ंक्शन का जो सार्वभौमिक के समीप है। | हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट ढूंढने के लिए रैखिक जांच का उपयोग करने के कारण होता है, न कि मूल रैखिक जांच हैश तालिका एल्गोरिदम के अनुसार प्रत्येक लुकअप के लिए। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल फ़ंक्शन का जो सार्वभौमिक के समीप है। | ||
Revision as of 14:42, 19 July 2023
हॉपस्कॉच हैशिंग कंप्यूटर प्रोग्रामिंग में ओपन एड्रेसिंग का उपयोग करके टेबल में हैश फंकशन के मूल्यों के हैश टकराव को हल करने की एक योजना है। यह समवर्ती हैश टेबल को कार्यान्वित करने के लिए भी उपयुक्त है। होपस्कॉच हैशिंग का प्रारम्भ 2008 में मौरिस हेर्लिही, नीर शवित और मोरन तज़ाफिर द्वारा की गई थी।[1] यह नाम हॉप्स के अनुक्रम से लिया गया है जो टेबल के सम्मिलन एल्गोरिथ्म को दर्शाता है।
एल्गोरिथ्म n बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका प्रतिवेश H लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही कैश लाइन के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(n) आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है।
हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली H−1 प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, H 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश "आभासी" बकेट है जिसका निश्चित आकार होता है और निम्नलिखित H−1 बकेट के साथ ओवरलैप होता है। सर्च को तेज़ करने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में "हॉप-सूचना" शब्द, एक H-बिट बिटमैप सम्मिलित होता है जो इंगित करता है कि अगली H−1 प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, शब्द को देखकर यह देखने के लिए कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करके एक आइटम को तुरंत पाया जा सकता है (अधिकांश आधुनिक प्रोसेसर विशेष बिट मैनिपुलेशन ऑपरेशन का समर्थन करते हैं जो "हॉप-सूचना" बिटमैप में लुकअप को बहुत तेज़ बनाते हैं)।
यहां बकेट i में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है:
- यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो टेबल भरी हुई है; हैश टेबल का विस्तार करें और पुनः प्रयास करें।
- प्रविष्टि i से प्रारम्भ करते हुए, सूचकांक j पर एक खाली प्रविष्टि खोजने के लिए एक रैखिक जांच का उपयोग करें। (यदि कोई खाली स्लॉट उपस्थित नहीं है, तो टेबल भरी हुई है।)
- जबकि (j−i) mod n ≥ H, खाली स्लॉट को i की ओर निम्नानुसार ले जाएं:
- किसी आइटम y के लिए j से पहले H−1 स्लॉट खोजें, जिसका हैश मान k, j के H−1 के भीतर है, अर्थात (j−k) mod n < H (यह हॉप-सूचना शब्दों का उपयोग करके किया जा सकता है।)
- यदि ऐसी कोई वस्तु y सीमा के भीतर उपस्थित नहीं है, तो टेबल भरी हुई है।
- y को j पर ले जाएं, i के करीब एक नया खाली स्लॉट बनाएं।
- j को y द्वारा खाली किए गए खाली स्लॉट पर सेट करें और दोहराएं।
- x को स्लॉट j में स्टोर करें और वापस लौटें।
विचार यह है कि हॉपस्कॉच हैशिंग "खाली स्लॉट को वांछित बकेट की ओर ले जाता है"। यह इसे रैखिक जांच से अलग करता है जो उस खाली स्लॉट को छोड़ देता है जहां यह पाया गया था, संभवतः मूल बकेट से बहुत दूर, या कोयल हैशिंग से, जो मुफ्त बकेट बनाने के लिए, वांछित बकेट में से किसी एक वस्तु को बाहर ले जाता है लक्ष्य सरणियाँ, और उसके बाद ही विस्थापित वस्तु को नई जगह खोजने की कोशिश करता है।
किसी आइटम को तालिका से हटाने के लिए, व्यक्ति बस उसे तालिका प्रविष्टि से हटा देता है। यदि पड़ोस की बकेट कैश संरेखित हैं, तो कोई पुनर्गठन ऑपरेशन लागू कर सकता है जिसमें संरेखण में सुधार करने के लिए आइटम को अब खाली स्थान पर ले जाया जाता है।
हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट ढूंढने के लिए रैखिक जांच का उपयोग करने के कारण होता है, न कि मूल रैखिक जांच हैश तालिका एल्गोरिदम के अनुसार प्रत्येक लुकअप के लिए। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल फ़ंक्शन का जो सार्वभौमिक के समीप है।
यह भी देखें
- कुकु हैशिंग
- हैश कोलेसन
- हैश फंक्शन
- लीनियर प्रोबिंग
- ओपन एड्रेसिंग
- परफेक्ट हैशिंग
- क्वाड्रैटिक प्रोबिंग
संदर्भ
- ↑ Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing" (PDF). DISC '08: Proceedings of the 22nd international symposium on Distributed Computing. Arcachon, France: Springer-Verlag. pp. 350–364.
बाहरी संबंध
- libhhash - a C hopscotch hashing implementation
- hopscotch-map - a C++ implementation of a hash map using hopscotch hashing
- Goossaert, Emmanuel (11 August 2013). "Hopscotch hashing". Retrieved 16 October 2019. A detailed description and example implementation.
