हॉप्सकॉच हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
}}</ref> यह नाम हॉप्स के अनुक्रम से लिया गया है जो टेबल के सम्मिलन एल्गोरिथ्म को दर्शाता है। | }}</ref> यह नाम हॉप्स के अनुक्रम से लिया गया है जो टेबल के सम्मिलन एल्गोरिथ्म को दर्शाता है। | ||
एल्गोरिथ्म n बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका | एल्गोरिथ्म ''n'' बकेट की एक एकल सरणी का उपयोग करता है। प्रत्येक बकेट के लिए, उसका ''प्रतिवेश'' ''H'' लगातार बकेट का एक छोटा संग्रह है (यानी मूल हैशेड बकेट के करीब सूचकांक वाले)। प्रतिवेश की वांछित गुण यह है कि प्रतिवेश की बकेट्स में किसी वस्तु को खोजने की लागत उसे बकेट में खोजने की लागत के करीब होती है (उदाहरण के लिए, प्रतिवेश में बकेट्स एक ही [[कैश लाइन]] के अंतर्गत आती हैं)। प्रतिवेश का आकार सबसे खराब स्थिति में आइटमों की लघुगणक संख्या को समायोजित करने के लिए पर्याप्त होना चाहिए (अर्थात इसमें log(''n'') आइटम को समायोजित करना होगा), लेकिन औसतन केवल एक स्थिर संख्या। यदि किसी बकेट का प्रतिवेश भर जाता है, तो टेबल का आकार बदल दिया जाता है। | ||
हॉप्सकॉच हैशिंग में, कूकू हैशिंग की तरह, और रैखिक जांच के विपरीत, एक दी गई वस्तु हमेशा डाली जाएगी और उसके हैशेड बकेट के प्रतिवेश में पाई जाएगी। दूसरे शब्दों में, यह हमेशा या तो इसकी मूल हैशेड सरणी प्रविष्टि में या अगली ''H−1'' प्रतिवेशी प्रविष्टियों में से एक में पाया जाएगा। उदाहरण के लिए, ''H'' 32 हो सकता है, जो एक सामान्य मशीन शब्द का आकार है। इस प्रकार प्रतिवेश एक "आभासी" बकेट है जिसका एक निश्चित आकार होता है और निम्नलिखित ''H−1'' बकेट के साथ ओवरलैप होता है। सर्च को तेज़ करने के लिए, प्रत्येक बकेट (सरणी प्रविष्टि) में एक "हॉप-सूचना" शब्द, एक ''H''-बिट बिटमैप शामिल होता है जो इंगित करता है कि अगली ''H−1'' प्रविष्टियों में से किसमें वे आइटम हैं जो वर्तमान प्रविष्टि की वर्चुअल बकेट में हैश किए गए हैं। इस तरह, शब्द को देखकर यह देखने के लिए कि कौन सी प्रविष्टियाँ बकेट से संबंधित हैं, और फिर प्रविष्टियों की निरंतर संख्या के माध्यम से स्कैन करके एक आइटम को तुरंत पाया जा सकता है (अधिकांश आधुनिक प्रोसेसर विशेष बिट मैनिपुलेशन ऑपरेशन का समर्थन करते हैं जो "हॉप-सूचना" बिटमैप में लुकअप को बहुत तेज़ बनाते हैं)। | |||
हॉप्सकॉच हैशिंग में, | |||
यहां बकेट i में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है: | यहां बकेट i में हैश किए गए आइटम x को जोड़ने का तरीका बताया गया है: | ||
| Line 30: | Line 27: | ||
विचार यह है कि हॉपस्कॉच हैशिंग खाली स्लॉट को वांछित बकेट की ओर ले जाती है। यह इसे रैखिक जांच से अलग करता है जो खाली स्लॉट को छोड़ देता है जहां यह पाया गया था, संभवतः मूल बकेट से बहुत दूर, या कोयल हैशिंग से, जो एक मुफ्त बकेट बनाने के लिए, वांछित बकेट में से एक वस्तु को बाहर ले जाता है लक्ष्य सरणियाँ, और उसके बाद ही विस्थापित वस्तु को एक नया स्थान खोजने का प्रयास करता है। | विचार यह है कि हॉपस्कॉच हैशिंग खाली स्लॉट को वांछित बकेट की ओर ले जाती है। यह इसे रैखिक जांच से अलग करता है जो खाली स्लॉट को छोड़ देता है जहां यह पाया गया था, संभवतः मूल बकेट से बहुत दूर, या कोयल हैशिंग से, जो एक मुफ्त बकेट बनाने के लिए, वांछित बकेट में से एक वस्तु को बाहर ले जाता है लक्ष्य सरणियाँ, और उसके बाद ही विस्थापित वस्तु को एक नया स्थान खोजने का प्रयास करता है। | ||
किसी आइटम को टेबल से हटाने के लिए, उसे बस टेबल प्रविष्टि से हटा दिया जाता है। यदि | किसी आइटम को टेबल से हटाने के लिए, उसे बस टेबल प्रविष्टि से हटा दिया जाता है। यदि प्रतिवेश की बकेट कैश संरेखित हैं, तो कोई पुनर्गठन ऑपरेशन लागू कर सकता है जिसमें संरेखण में सुधार के लिए वस्तुओं को अब खाली स्थान पर ले जाया जाता है। | ||
हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक वाले कारकों पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट खोजने के लिए एक रैखिक जांच का उपयोग करने के कारण होता है, मूल रैखिक जांच हैश टेबल एल्गोरिदम की तरह हर लुकअप के लिए नहीं। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल जो सार्वभौमिक के करीब हैं। | हॉप्सकॉच हैशिंग का एक फायदा यह है कि यह बहुत उच्च टेबल लोड कारकों पर भी अच्छा प्रदर्शन प्रदान करता है, यहां तक कि 0.9 से अधिक वाले कारकों पर भी। इस दक्षता का एक हिस्सा केवल सम्मिलन के दौरान एक खाली स्लॉट खोजने के लिए एक रैखिक जांच का उपयोग करने के कारण होता है, मूल रैखिक जांच हैश टेबल एल्गोरिदम की तरह हर लुकअप के लिए नहीं। एक अन्य लाभ यह है कि कोई भी किसी भी हैश फ़ंक्शन का उपयोग कर सकता है, विशेष रूप से सरल जो सार्वभौमिक के करीब हैं। | ||
Revision as of 14:29, 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.
