ओपन एड्रेसिंग
ओपन एड्रेसिंग, या क्लोज्ड हैशिंग, हैश टेबल#टकराव समाधान की एक विधि है। इस पद्धति के साथ हैश टकराव को जांच करके, या सरणी में वैकल्पिक स्थानों ('जांच अनुक्रम') के माध्यम से खोज कर हल किया जाता है जब तक कि लक्ष्य रिकॉर्ड नहीं मिल जाता है, या अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो इंगित करता है कि कोई नहीं है तालिका में ऐसी कुंजी.[1] प्रसिद्ध जांच अनुक्रमों में शामिल हैं:
- रैखिक जांच
- जिसमें जांच के बीच का अंतराल निश्चित होता है — अक्सर 1 पर सेट किया जाता है।
- द्विघात जांच
- जिसमें जांच के बीच का अंतराल द्विघात रूप से बढ़ता है (इसलिए, सूचकांकों को द्विघात फ़ंक्शन द्वारा वर्णित किया जाता है)।
- डबल हैशिंग
- जिसमें प्रत्येक रिकॉर्ड के लिए जांच के बीच का अंतराल तय किया जाता है लेकिन इसकी गणना किसी अन्य हैश फ़ंक्शन द्वारा की जाती है।
इन विधियों के बीच मुख्य व्यापार यह है कि रैखिक जांच में संदर्भ की सबसे अच्छी स्थानीयता होती है, लेकिन क्लस्टरिंग के प्रति सबसे अधिक संवेदनशील होती है, जबकि डबल हैशिंग में कैश प्रदर्शन खराब होता है, लेकिन वस्तुतः कोई क्लस्टरिंग प्रदर्शित नहीं होती है; दोनों क्षेत्रों में द्विघात जांच बीच में आती है। डबल हैशिंग के लिए अन्य प्रकार की जांच की तुलना में अधिक गणना की भी आवश्यकता हो सकती है।
कुछ खुले संबोधन के तरीके, जैसे हॉप्सकॉच हैशिंग, हैश टेबल#रॉबिन हुड हैशिंग, अंतिम-आओ-पहले पाओ हैशिंग और कोयल हैशिंग नई कुंजी के लिए जगह बनाने के लिए मौजूदा कुंजियों को सरणी में इधर-उधर ले जाती है। यह जांच पर आधारित तरीकों की तुलना में बेहतर अधिकतम खोज समय देता है। [2][3][4][5][6] ओपन एड्रेसिंग हैश टेबल के प्रदर्शन पर एक महत्वपूर्ण प्रभाव लोड फैक्टर है; अर्थात्, उपयोग की जाने वाली सरणी में स्लॉट का अनुपात। जैसे-जैसे लोड फैक्टर 100% की ओर बढ़ता है, किसी दी गई कुंजी को खोजने या डालने के लिए आवश्यक जांचों की संख्या नाटकीय रूप से बढ़ जाती है। एक बार जब तालिका पूरी हो जाती है, तो जांच एल्गोरिदम समाप्त होने में भी विफल हो सकता है। अच्छे हैश फ़ंक्शन के साथ भी, लोड कारक सामान्यतः 80% तक सीमित होते हैं। एक खराब हैश फ़ंक्शन महत्वपूर्ण क्लस्टरिंग उत्पन्न करके बहुत कम लोड कारकों पर भी खराब प्रदर्शन प्रदर्शित कर सकता है, खासकर सबसे सरल रैखिक एड्रेसिंग विधि के साथ। आम तौर पर अधिकांश ओपन एड्रेसिंग विधियों के साथ विशिष्ट लोड कारक 50% होते हैं, जबकि हैश_टेबल#सेपरेट_चेनिंग आमतौर पर 100% तक का उपयोग कर सकते हैं।
उदाहरण छद्मकोड
निम्नलिखित छद्मकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक ओपन एड्रेसिंग हैश तालिका का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।
रिकॉर्ड जोड़ी { कुंजी, मान, अधिकृत ध्वज (प्रारंभ में अनसेट) }
वर जोड़ी स्लॉट[0], स्लॉट[1], ..., स्लॉट[num_slots - 1]
फ़ंक्शन ढूंढें_स्लॉट(कुंजी)
i := हैश(कुंजी) मॉड्यूलो num_slots
// तब तक खोजें जब तक हमें या तो चाबी न मिल जाए, या कोई खाली स्लॉट न मिल जाए।
जबकि (स्लॉट[i] भरा हुआ है) और (स्लॉट[i].कुंजी ≠ कुंजी)
i := (i + 1) मॉड्यूलो num_slots
वापसी मैं
फ़ंक्शन लुकअप (कुंजी)
मैं := खोज_स्लॉट(कुंजी)
यदि स्लॉट[i] भरा हुआ है //कुंजी तालिका में है
रिटर्न स्लॉट[i].वैल्यू
अन्यथा //कुंजी तालिका में नहीं है
रिटर्न नहीं मिला
फ़ंक्शन सेट (कुंजी, मान)
मैं := खोज_स्लॉट(कुंजी)
यदि स्लॉट[i] पर कब्जा है // हमें हमारी कुंजी मिल गई
स्लॉट[i].मूल्य = मूल्य
वापस करना
यदि तालिका लगभग भरी हुई है
बड़ी तालिका का पुनर्निर्माण करें (नोट 1)
मैं := खोज_स्लॉट(कुंजी)
स्लॉट[i] को कब्जे में के रूप में चिह्नित करें
स्लॉट[i].कुंजी = कुंजी
स्लॉट[i].मूल्य = मूल्य
- नोट 1
- तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में घातीय वृद्धि करना आम बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।
फ़ंक्शन हटाएँ (कुंजी)
मैं := खोज_स्लॉट(कुंजी)
यदि स्लॉट[i] खाली है
वापसी //कुंजी तालिका में नहीं है
स्लॉट[i] को रिक्त के रूप में चिह्नित करें
जे := मैं
लूप (नोट 2)
जे := (जे + 1) मॉड्यूलो संख्या_स्लॉट
यदि स्लॉट[जे] खाली है
निकास पाश
k := हैश(स्लॉट[j].key) मॉड्यूलो num_slots
// निर्धारित करें कि क्या k चक्रीय रूप से (i,j] में स्थित है
// i ≤ j: | मैं..के..जे |
// i > j: |.k..j i....| या |...जे आई..के.|
अगर मैं ≤ जे
यदि (i < k) और (k ≤ j)
लूप जारी रखें
अन्य
यदि (i < k) या (k ≤ j)
लूप जारी रखें
स्लॉट[i] := स्लॉट[j]
स्लॉट[जे] को रिक्त के रूप में चिह्नित करें
मैं := जे
- नोट 2
- क्लस्टर में सभी रिकॉर्ड के लिए, उनकी प्राकृतिक हैश स्थिति और उनकी वर्तमान स्थिति के बीच कोई खाली स्लॉट नहीं होना चाहिए (अन्यथा लुकअप रिकॉर्ड ढूंढने से पहले ही समाप्त हो जाएगा)। छद्मकोड में इस बिंदु पर, i एक खाली स्लॉट है जो क्लस्टर में बाद के रिकॉर्ड के लिए इस संपत्ति को अमान्य कर सकता है। j ऐसा अगला रिकॉर्ड है. k कच्चा हैश है जहां रिकॉर्ड है {{var|j}यदि कोई टकराव न हो तो } स्वाभाविक रूप से हैश तालिका में आ जाएगा। यह परीक्षण पूछ रहा है कि क्या रिकॉर्ड है j अब क्लस्टर के आवश्यक गुणों के संबंध में अमान्य रूप से स्थित है i रिक्त है.
हटाने की एक अन्य तकनीक बस स्लॉट को हटाए गए के रूप में चिह्नित करना है। हालाँकि अंततः हटाए गए रिकॉर्ड को हटाने के लिए तालिका को फिर से बनाने की आवश्यकता होती है। उपरोक्त विधियाँ O(1) को अद्यतन करने और मौजूदा रिकॉर्ड को हटाने की सुविधा प्रदान करती हैं, साथ ही यदि तालिका आकार का उच्च-जल चिह्न बढ़ता है तो कभी-कभी पुनर्निर्माण भी किया जाता है।
उपरोक्त O(1) हटाने की विधि केवल सिंगल-स्लॉट स्टेपिंग के साथ रैखिक रूप से जांच की गई हैश तालिकाओं में ही संभव है। ऐसे मामले में जहां एक ऑपरेशन में कई रिकॉर्ड हटाए जाने हैं, हटाने और बाद में पुनर्निर्माण के लिए स्लॉट चिह्नित करना अधिक कुशल हो सकता है।
यह भी देखें
- आलसी विलोपन - खुले पते का उपयोग करके हैश तालिका से हटाने की एक विधि।
संदर्भ
- ↑ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990), Data Structures Using C, Prentice Hall, pp. 456–461, pp. 472, ISBN 0-13-199746-7
- ↑ Poblete; Viola; Munro. "The Analysis of a Hashing Scheme by the Diagonal Poisson Transform". p. 95 of Jan van Leeuwen (Ed.) "Algorithms - ESA '94". 1994.
- ↑ Steve Heller. "Efficient C/C++ Programming: Smaller, Faster, Better" 2014. p. 33.
- ↑ Patricio V. Poblete, Alfredo Viola. "Robin Hood Hashing really has constant average search cost and variance in full tables". 2016.
- ↑ Paul E. Black, "Last-Come First-Served Hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
- ↑ Paul E. Black, "Robin Hood hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
