हॉप्सकॉच हैशिंग: Difference between revisions

From Vigyanwiki
(Created page with "Image:hopscotch-wiki-example.gif|thumb|upright=2.5| हॉप्सकॉच हैशिंग। यहाँ, H 4 है। ग्रे प्रविष्टिया...")
 
No edit summary
 
(7 intermediate revisions by 4 users not shown)
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 जोड़ने से ठीक पहले तालिका स्थिति दिखाता है।]]हॉप्सकॉच हैशिंग [[कंप्यूटर प्रोग्रामिंग]] में [[ खुला संबोधन ]] का उपयोग करके [[हैश तालिका]] में [[हैश फंकशन]] के मूल्यों के हैश टकराव को हल करने की एक योजना है। यह [[समवर्ती हैश तालिका]] को लागू करने के लिए भी उपयुक्त है। होपस्कॉच हैशिंग की शुरुआत 2008 में [[मौरिस हेर्लिही]], [[नीर शवित]] और मोरन तज़ाफ़र द्वारा की गई थी।<ref>{{cite conference
[[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 8: Line 8:
  |location=Arcachon, France |publisher=Springer-Verlag
  |location=Arcachon, France |publisher=Springer-Verlag
  |url=http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf
  |url=http://mcg.cs.tau.ac.il/papers/disc2008-hopscotch.pdf
}}</ref> यह नाम हॉप्स के अनुक्रम से लिया गया है जो तालिका के सम्मिलन एल्गोरिदम की विशेषता बताता है।
}}</ref> यह नाम हॉप्स के अनुक्रम से लिया गया है जो टेबल के सम्मिलन एल्गोरिथ्म को दर्शाता है।


एल्गोरिथ्म n बकेट की एकल सरणी का उपयोग करता है। प्रत्येक बाल्टी के लिए, उसका पड़ोस एच लगातार बाल्टी का एक छोटा संग्रह है (यानी मूल हैश बाल्टी के करीब सूचकांक वाले)। पड़ोस की वांछित संपत्ति यह है कि पड़ोस की बाल्टियों में किसी वस्तु को खोजने की लागत उसे बाल्टी में खोजने की लागत के करीब है (उदाहरण के लिए, पड़ोस में बाल्टियाँ एक ही [[कैश लाइन]] के भीतर आती हैं)। पड़ोस का आकार सबसे खराब स्थिति में आइटमों की लघुगणकीय संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (यानी इसमें लॉग (एन) आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि कुछ बाल्टी का पड़ोस भर जाता है, तो टेबल का आकार बदल दिया जाता है।
एल्गोरिथ्म ''n'' बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका ''प्रतिवेश'' ''H'' लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही [[कैश लाइन]] के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(''n'') आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है।


हॉप्सकॉच हैशिंग में, [[कोयल हैशिंग]] की तरह, और [[रैखिक जांच]] के विपरीत, किसी दिए गए आइटम को हमेशा उसके हैशेड बाल्टी के पड़ोस में डाला और पाया जाएगा। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में, या अगली H−1 पड़ोसी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, H 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार पड़ोस एक आभासी बाल्टी है जिसका आकार निश्चित है और निम्नलिखित H−1 बाल्टियों के साथ ओवरलैप होता है। खोज को गति देने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में एक हॉप-सूचना शब्द, एक एच-बिट बिटमैप शामिल होता है जो इंगित करता है कि अगली H−1 प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, किसी आइटम को शब्द को देखकर जल्दी से पाया जा सकता है कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करना (अधिकांश आधुनिक प्रोसेसर विशेष बिट हेरफेर संचालन का समर्थन करते हैं जो हॉप में लुकअप करते हैं- सूचना बिटमैप बहुत तेज़)।
हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली ''H−1'' प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, ''H'' 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश "आभासी" बकेट है जिसका निश्चित आकार होता है और निम्नलिखित ''H−1'' बकेट के साथ ओवरलैप होता है। सर्च को तेज़ करने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में "हॉप-सूचना" शब्द, एक ''H''-बिट बिटमैप सम्मिलित होता है जो इंगित करता है कि अगली ''H''−1 प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, शब्द को देखकर यह देखने के लिए कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करके एक आइटम को तुरंत पाया जा सकता है (अधिकांश आधुनिक प्रोसेसर विशेष बिट मैनिपुलेशन ऑपरेशन का समर्थन करते हैं जो "हॉप-सूचना" बिटमैप में लुकअप को बहुत तेज़ बनाते हैं)।


यहां बकेट i में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है:
यहां बकेट ''i'' में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है:


# यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो तालिका भरी हुई है; हैश तालिका का विस्तार करें और पुनः प्रयास करें।
# यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो टेबल भरी हुई है; हैश टेबल का विस्तार करें और पुनः प्रयास करें।
# प्रविष्टि i से शुरू करते हुए, सूचकांक j पर एक खाली प्रविष्टि खोजने के लिए एक रैखिक जांच का उपयोग करें। (यदि कोई खाली स्लॉट मौजूद नहीं है, तो तालिका भरी हुई है।)
# प्रविष्टि ''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 से अधिक पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट ढूंढने के लिए रैखिक जांच का उपयोग करने के कारण होता है, न कि मूल रैखिक जांच हैश तालिका एल्गोरिदम के अनुसार प्रत्येक लुकअप के लिए। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल फ़ंक्शन का जो सार्वभौमिक के समीप है।


== यह भी देखें ==
== यह भी देखें ==


* कोयल हैशिंग
* कुकु हैशिंग  
* हैश टकराव
* हैश कोलेसन
* हैश फंकशन
* हैश फंक्शन
*रेखीय जांच
* लीनियर प्रोबिंग
* हैश_टेबल#ओपन_एड्रेसिंग
* ओपन एड्रेसिंग
* उत्तम हैशिंग
* परफेक्ट हैशिंग  
* [[द्विघात जांच]]
* क्वाड्रैटिक प्रोबिंग


== संदर्भ ==
== संदर्भ ==
Line 50: Line 50:
*[https://github.com/Tessil/hopscotch-map hopscotch-map - a C++ implementation of a hash map using hopscotch hashing]
*[https://github.com/Tessil/hopscotch-map hopscotch-map - a C++ implementation of a hash map using hopscotch hashing]
* {{cite web |title=Hopscotch hashing |first=Emmanuel |last=Goossaert |date=11 August 2013 |access-date=16 October 2019 |url=http://codecapsule.com/2013/08/11/hopscotch-hashing/}} A detailed description and example implementation.
* {{cite web |title=Hopscotch hashing |first=Emmanuel |last=Goossaert |date=11 August 2013 |access-date=16 October 2019 |url=http://codecapsule.com/2013/08/11/hopscotch-hashing/}} A detailed description and example implementation.
[[Category: एल्गोरिदम खोजें]] [[Category: हैशिंग]]


[[Category: Machine Translated Page]]
[[Category:Created On 11/07/2023]]
[[Category:Created On 11/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with broken file links]]
[[Category:Templates Vigyan Ready]]
[[Category:एल्गोरिदम खोजें]]
[[Category:हैशिंग]]

Latest revision as of 10:01, 2 August 2023

File:Hopscotch-wiki-example.gif
हॉप्सकॉच हैशिंग। यहाँ, 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 में मौरिस हेर्लिही, नीर शवित और मोरन तज़ाफिर द्वारा की गई थी।[1] यह नाम हॉप्स के अनुक्रम से लिया गया है जो टेबल के सम्मिलन एल्गोरिथ्म को दर्शाता है।

एल्गोरिथ्म n बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका प्रतिवेश H लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही कैश लाइन के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(n) आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है।

हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली H−1 प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, H 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश "आभासी" बकेट है जिसका निश्चित आकार होता है और निम्नलिखित H−1 बकेट के साथ ओवरलैप होता है। सर्च को तेज़ करने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में "हॉप-सूचना" शब्द, एक H-बिट बिटमैप सम्मिलित होता है जो इंगित करता है कि अगली H−1 प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, शब्द को देखकर यह देखने के लिए कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करके एक आइटम को तुरंत पाया जा सकता है (अधिकांश आधुनिक प्रोसेसर विशेष बिट मैनिपुलेशन ऑपरेशन का समर्थन करते हैं जो "हॉप-सूचना" बिटमैप में लुकअप को बहुत तेज़ बनाते हैं)।

यहां बकेट i में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है:

  1. यदि बकेट आई के लिए हॉप-सूचना शब्द दिखाता है कि इस बकेट में पहले से ही एच आइटम हैं, तो टेबल भरी हुई है; हैश टेबल का विस्तार करें और पुनः प्रयास करें।
  2. प्रविष्टि i से प्रारम्भ करते हुए, सूचकांक j पर एक खाली प्रविष्टि खोजने के लिए एक रैखिक जांच का उपयोग करें। (यदि कोई खाली स्लॉट उपस्थित नहीं है, तो टेबल भरी हुई है।)
  3. जबकि (j−i) mod n ≥ H, खाली स्लॉट को i की ओर निम्नानुसार ले जाएं:
    1. किसी आइटम y के लिए j से पहले H−1 स्लॉट खोजें, जिसका हैश मान k, j के H−1 के भीतर है, अर्थात (j−k) mod n < H (यह हॉप-सूचना शब्दों का उपयोग करके किया जा सकता है।)
    2. यदि ऐसी कोई वस्तु y सीमा के भीतर उपस्थित नहीं है, तो टेबल भरी हुई है।
    3. y को j पर ले जाएं, i के करीब एक नया खाली स्लॉट बनाएं।
    4. j को y द्वारा खाली किए गए खाली स्लॉट पर सेट करें और दोहराएं।
  4. x को स्लॉट j में स्टोर करें और वापस लौटें।

विचार यह है कि हॉपस्कॉच हैशिंग "खाली स्लॉट को वांछित बकेट की ओर ले जाता है"। यह इसे रैखिक जांच से अलग करता है जो उस खाली स्लॉट को छोड़ देता है जहां यह पाया गया था, संभवतः मूल बकेट से बहुत दूर, या कोयल हैशिंग से, जो मुफ्त बकेट बनाने के लिए, वांछित बकेट में से किसी एक वस्तु को बाहर ले जाता है लक्ष्य सरणियाँ, और उसके बाद ही विस्थापित वस्तु को नई जगह खोजने की कोशिश करता है।

किसी आइटम को तालिका से हटाने के लिए, व्यक्ति बस उसे तालिका प्रविष्टि से हटा देता है। यदि पड़ोस की बकेट कैश संरेखित हैं, तो कोई पुनर्गठन ऑपरेशन लागू कर सकता है जिसमें संरेखण में सुधार करने के लिए आइटम को अब खाली स्थान पर ले जाया जाता है।

हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट ढूंढने के लिए रैखिक जांच का उपयोग करने के कारण होता है, न कि मूल रैखिक जांच हैश तालिका एल्गोरिदम के अनुसार प्रत्येक लुकअप के लिए। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल फ़ंक्शन का जो सार्वभौमिक के समीप है।

यह भी देखें

  • कुकु हैशिंग
  • हैश कोलेसन
  • हैश फंक्शन
  • लीनियर प्रोबिंग
  • ओपन एड्रेसिंग
  • परफेक्ट हैशिंग
  • क्वाड्रैटिक प्रोबिंग

संदर्भ

  1. ↑ 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.


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=हॉप्सकॉच_हैशिंग&oldid=232933’