हॉप्सकॉच हैशिंग

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 में मौरिस हेर्लिही, नीर शवित और मोरन तज़ाफ़र द्वारा की गई थी। यह नाम हॉप्स के अनुक्रम से लिया गया है जो तालिका के सम्मिलन एल्गोरिदम की विशेषता बताता है।

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

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

यह भी देखें

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

बाहरी संबंध

• 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.