ओपन एड्रेसिंग: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Hash collision resolution technique}} Image:HASHTB12.svg|thumb|362px|right|हैश टकराव को रैखिक जांच (अंतरा...")
 
No edit summary
Line 1: Line 1:
{{Short description|Hash collision resolution technique}}
{{Short description|Hash collision resolution technique}}
[[Image:HASHTB12.svg|thumb|362px|right|हैश टकराव को रैखिक जांच (अंतराल = 1) द्वारा हल किया गया।]]ओपन एड्रेसिंग, या क्लोज्ड हैशिंग, हैश टेबल#टकराव समाधान की एक विधि है। इस पद्धति के साथ हैश टकराव को जांच करके, या सरणी में वैकल्पिक स्थानों ('जांच अनुक्रम') के माध्यम से खोज कर हल किया जाता है जब तक कि लक्ष्य रिकॉर्ड नहीं मिल जाता है, या अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो इंगित करता है कि कोई नहीं है तालिका में ऐसी कुंजी.<ref name="tenenbaum90">{{Citation | title=Data Structures Using C | first1=Aaron M. | last1=Tenenbaum | first2=Yedidyah | last2=Langsam | first3=Moshe J. | last3=Augenstein | publisher=Prentice Hall | year=1990 | isbn=0-13-199746-7 | pages=456–461, pp. 472}}</ref> प्रसिद्ध जांच अनुक्रमों में शामिल हैं:
[[Image:HASHTB12.svg|thumb|362px|right|हैश टकराव को रैखिक जांच (अंतराल = 1) द्वारा हल किया गया।]]विवर्त संबोधन, या क्लोज्ड हैशिंग, हैश टेबल टकराव समाधान की एक विधि है। इस पद्धति के साथ हैश टकराव को जांच करके, या सरणी में वैकल्पिक स्थानों ('जांच अनुक्रम') के माध्यम से खोज कर हल किया जाता है जब तक कि लक्ष्य रिकॉर्ड नहीं मिल जाता है, या अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो निरुपित करता है कि कोई नहीं है तालिका में ऐसी कुंजी.<ref name="tenenbaum90">{{Citation | title=Data Structures Using C | first1=Aaron M. | last1=Tenenbaum | first2=Yedidyah | last2=Langsam | first3=Moshe J. | last3=Augenstein | publisher=Prentice Hall | year=1990 | isbn=0-13-199746-7 | pages=456–461, pp. 472}}</ref> प्रसिद्ध जांच अनुक्रमों में सम्मिलित हैं:


; [[रैखिक जांच]]: जिसमें जांच के बीच का अंतराल निश्चित होता है — अक्सर 1 पर सेट किया जाता है।
; [[रैखिक जांच]]: जिसमें जांच के बीच का अंतराल निश्चित होता है — अधिकांशत:1 पर सेट किया जाता है।
; [[द्विघात जांच]]: जिसमें जांच के बीच का अंतराल द्विघात रूप से बढ़ता है (इसलिए, सूचकांकों को द्विघात फ़ंक्शन द्वारा वर्णित किया जाता है)।
; [[द्विघात जांच]]: जिसमें जांच के बीच का अंतराल द्विघात रूप से बढ़ता है (इसलिए, सूचकांकों को द्विघात फ़ंक्शन द्वारा वर्णित किया जाता है)।
; [[डबल हैशिंग]]: जिसमें प्रत्येक रिकॉर्ड के लिए जांच के बीच का अंतराल तय किया जाता है लेकिन इसकी गणना किसी अन्य हैश फ़ंक्शन द्वारा की जाती है।
; [[डबल हैशिंग]]: जिसमें प्रत्येक रिकॉर्ड के लिए जांच के बीच का अंतराल तय किया जाता है किंतु इसकी गणना किसी अन्य हैश फ़ंक्शन द्वारा की जाती है।


इन विधियों के बीच मुख्य व्यापार यह है कि रैखिक जांच में संदर्भ की सबसे अच्छी स्थानीयता होती है, लेकिन क्लस्टरिंग के प्रति सबसे अधिक संवेदनशील होती है, जबकि डबल हैशिंग में कैश प्रदर्शन खराब होता है, लेकिन वस्तुतः कोई क्लस्टरिंग प्रदर्शित नहीं होती है; दोनों क्षेत्रों में द्विघात जांच बीच में आती है। डबल हैशिंग के लिए अन्य प्रकार की जांच की तुलना में अधिक गणना की भी आवश्यकता हो सकती है।
इन विधियों के बीच मुख्य व्यापार यह है कि रैखिक जांच में संदर्भ की सबसे अच्छी स्थानीयता होती है, किंतु क्लस्टरिंग के प्रति सबसे अधिक संवेदनशील होती है, जबकि डबल हैशिंग में कैश प्रदर्शन खराब होता है, किंतु वस्तुतः कोई क्लस्टरिंग प्रदर्शित नहीं होती है; दोनों क्षेत्रों में द्विघात जांच बीच में आती है। डबल हैशिंग के लिए अन्य प्रकार की जांच की तुलना में अधिक गणना की भी आवश्यकता हो सकती है।


कुछ खुले संबोधन के तरीके, जैसे
कुछ खुली एड्रेसिंग विधियाँ, जैसे होप्सकॉच हैशिंग, रॉबिन हुड हैशिंग, लास्ट-आओ-फर्स्ट-पाओ हैशिंग और कुक्कू हैशिंग नई कुंजी के लिए जगह बनाने के लिए उपस्थित कुंजियों को सरणी में इधर-उधर ले जाती हैं। यह जांच पर आधारित विधियों की तुलना में उत्तम अधिकतम खोज समय देता है
[[हॉप्सकॉच हैशिंग]],
हैश टेबल#रॉबिन हुड हैशिंग,
[[अंतिम-आओ-पहले पाओ हैशिंग]] और [[कोयल हैशिंग]] नई कुंजी के लिए जगह बनाने के लिए मौजूदा कुंजियों को सरणी में इधर-उधर ले जाती है। यह जांच पर आधारित तरीकों की तुलना में बेहतर अधिकतम खोज समय देता है।
<ref>
<ref>
Poblete; Viola; Munro.
Poblete; Viola; Munro.
Line 33: Line 30:
Paul E. Black, [https://www.nist.gov/dads/HTML/robinHoodHashing.html "Robin Hood hashing"], in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
Paul E. Black, [https://www.nist.gov/dads/HTML/robinHoodHashing.html "Robin Hood hashing"], in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
</ref>
</ref>
ओपन एड्रेसिंग हैश टेबल के प्रदर्शन पर एक महत्वपूर्ण प्रभाव लोड फैक्टर है; अर्थात्, उपयोग की जाने वाली सरणी में स्लॉट का अनुपात। जैसे-जैसे लोड फैक्टर 100% की ओर बढ़ता है, किसी दी गई कुंजी को खोजने या डालने के लिए आवश्यक जांचों की संख्या नाटकीय रूप से बढ़ जाती है। एक बार जब तालिका पूरी हो जाती है, तो जांच एल्गोरिदम समाप्त होने में भी विफल हो सकता है। अच्छे हैश फ़ंक्शन के साथ भी, लोड कारक सामान्यतः 80% तक सीमित होते हैं। एक खराब हैश फ़ंक्शन महत्वपूर्ण क्लस्टरिंग उत्पन्न करके बहुत कम लोड कारकों पर भी खराब प्रदर्शन प्रदर्शित कर सकता है, खासकर सबसे सरल रैखिक एड्रेसिंग विधि के साथ। आम तौर पर अधिकांश ओपन एड्रेसिंग विधियों के साथ विशिष्ट लोड कारक 50% होते हैं, जबकि हैश_टेबल#सेपरेट_चेनिंग आमतौर पर 100% तक का उपयोग कर सकते हैं।
 
विवर्त संबोधन हैश टेबल के प्रदर्शन पर एक महत्वपूर्ण प्रभाव लोड कारक है; अर्थात्, उपयोग की जाने वाली सरणी में स्लॉट का अनुपात जैसे-जैसे लोड कारक 100% की ओर बढ़ता है, किसी दी गई कुंजी को खोजने या डालने के लिए आवश्यक जांचों की संख्या नाटकीय रूप से बढ़ जाती है। एक बार जब तालिका पूरी हो जाती है, तो जांच एल्गोरिदम समाप्त होने में भी विफल हो सकता है। अच्छे हैश फ़ंक्शन के साथ भी, लोड कारक सामान्यतः 80% तक सीमित होते हैं। एक खराब हैश फ़ंक्शन महत्वपूर्ण क्लस्टरिंग उत्पन्न करके बहुत कम लोड कारकों पर भी व्यर्थ प्रदर्शन प्रदर्शित कर सकता है, विशेष रूप से सबसे सरल रैखिक एड्रेसिंग विधि के साथ समान्य रूप से अधिकांश विवर्त संबोधन विधियों के साथ विशिष्ट लोड कारक 50% होते हैं, जबकि हैश_टेबल या सेपरेट_चेनिंग समान्यत: 100% तक का उपयोग कर सकते हैं।


==उदाहरण [[छद्मकोड]]==
==उदाहरण [[छद्मकोड]]==


निम्नलिखित छद्मकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक ओपन एड्रेसिंग हैश तालिका का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।
निम्नलिखित छद्मकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक विवर्त संबोधन हैश तालिका का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।<syntaxhighlight>
 
record pair { key, value, occupied flag (initially unset) }
रिकॉर्ड जोड़ी { कुंजी, मान, अधिकृत ध्वज (प्रारंभ में अनसेट) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]
वर जोड़ी स्लॉट[0], स्लॉट[1], ..., स्लॉट[num_slots - 1]
function find_slot(key)
 
    i := hash(key) modulo num_slots
फ़ंक्शन ढूंढें_स्लॉट(कुंजी)
    // search until we either find the key, or find an empty slot.
    i := हैश(कुंजी) मॉड्यूलो num_slots
    while (slot[i] is occupied) and (slot[i].key ≠ key)
    ''// तब तक खोजें जब तक हमें या तो चाबी न मिल जाए, या कोई खाली स्लॉट न मिल जाए।''
        i := (i + 1) modulo num_slots
    जबकि (स्लॉट[i] भरा हुआ है) और (स्लॉट[i].कुंजी ≠ कुंजी)
    return i
        i := (i + 1) मॉड्यूलो num_slots
function lookup(key)
    वापसी मैं
    i := find_slot(key)
    if slot[i] is occupied  // key is in table
        return slot[i].value
    else                    // key is not in table
        return not found
function set(key, value)
    i := find_slot(key)
    if slot[i] is occupied  // we found our key
        slot[i].value = value
        return
    if the table is almost full
        rebuild the table larger (note 1)
        i := find_slot(key)
    mark slot[i] as occupied
    slot[i].key = key
    slot[i].value = value


फ़ंक्शन लुकअप (कुंजी)
    मैं := खोज_स्लॉट(कुंजी)
    यदि स्लॉट[i] भरा हुआ है ''//कुंजी तालिका में है''
        रिटर्न स्लॉट[i].वैल्यू
    अन्यथा ''//कुंजी तालिका में नहीं है''
        रिटर्न नहीं मिला


फ़ंक्शन सेट (कुंजी, मान)
                                                                                                                                                                             
    मैं := खोज_स्लॉट(कुंजी)
                                                                                                                                                                   
    यदि स्लॉट[i] पर कब्जा है ''// हमें हमारी कुंजी मिल गई''
                                                                                                                               
        स्लॉट[i].मूल्य = मूल्य
                                                                                                         
        वापस करना
                                                                                                                                                 
    यदि तालिका लगभग भरी हुई है
                                                                                                               
        बड़ी तालिका का पुनर्निर्माण करें ''(नोट 1)''
                                                                                                                                                           
        मैं := खोज_स्लॉट(कुंजी)
                                                                                                           
    स्लॉट[i] को कब्जे में के रूप में चिह्नित करें
</syntaxhighlight>
    स्लॉट[i].कुंजी = कुंजी
    स्लॉट[i].मूल्य = मूल्य


; नोट 1: तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना आम बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।
; नोट 1: तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना आम बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।: <syntaxhighlight>
function remove(key)
    i := find_slot(key)
    if slot[i] is unoccupied
        return  // key is not in the table
    mark slot[i] as unoccupied
    j := i
    loop (note 2)
        j := (j + 1) modulo num_slots
        if slot[j] is unoccupied
            exit loop
        k := hash(slot[j].key) modulo num_slots
        // determine if k lies cyclically in (i,j]
        // i ≤ j: |    i..k..j    |
        // i > j: |.k..j    i....| or |....j    i..k.|
        if i ≤ j
            if (i < k) and (k ≤ j)
                continue loop
        else
            if (i < k) or (k ≤ j)
                continue loop
        slot[i] := slot[j]
        mark slot[j] as unoccupied
        i := j                                                                                     
                                                                                                                 
                                                                                                                             
                                                                                                         
                                                                                                                 
                                                                                                   
                                                                                                         
                                                                                                         
                                                                                                     
                                                                                                     
                                                                                                 
</syntaxhighlight>


  फ़ंक्शन हटाएँ (कुंजी)
   
    मैं := खोज_स्लॉट(कुंजी)
    यदि स्लॉट[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: क्लस्टर में सभी रिकॉर्ड के लिए, उनकी प्राकृतिक हैश स्थिति और उनकी वर्तमान स्थिति के बीच कोई खाली स्लॉट नहीं होना चाहिए (अन्यथा लुकअप रिकॉर्ड ढूंढने से पहले ही समाप्त हो जाएगा)। छद्मकोड में इस बिंदु पर, {{var|i}} एक खाली स्लॉट है जो क्लस्टर में बाद के रिकॉर्ड के लिए इस संपत्ति को अमान्य कर सकता है। {{var|j}} ऐसा अगला रिकॉर्ड है. {{var|k}} कच्चा हैश है जहां रिकॉर्ड है {{var|j}यदि कोई टकराव न हो तो } स्वाभाविक रूप से हैश तालिका में आ जाएगा। यह परीक्षण पूछ रहा है कि क्या रिकॉर्ड है {{var|j}} अब क्लस्टर के आवश्यक गुणों के संबंध में अमान्य रूप से स्थित है {{var|i}} रिक्त है.
; नोट 2:क्लस्टर में सभी रिकॉर्ड के लिए, उनकी प्राकृतिक हैश स्थिति और उनकी वर्तमान स्थिति के बीच कोई रिक्त स्लॉट नहीं होना चाहिए (अन्यथा लुकअप रिकॉर्ड खोजने से पहले ही समाप्त हो जाएगा)। छद्मकोड में इस बिंदु पर, i एक रिक्त स्लॉट है जो क्लस्टर में पश्चात् के रिकॉर्ड के लिए इस गुण को अमान्य कर सकता है। j एक ऐसा अनुवर्ती रिकॉर्ड है। k राव हैश है जहां कोई टकराव न होने पर j पर रिकॉर्ड स्वाभाविक रूप से हैश तालिका में आ जाएगा। यह परीक्षण पूछ रहा है कि क्या j पर रिकॉर्ड क्लस्टर के आवश्यक गुणों के संबंध में अमान्य रूप से स्थित है, क्योंकि अब i रिक्त है।


हटाने की एक अन्य तकनीक बस स्लॉट को हटाए गए के रूप में चिह्नित करना है। हालाँकि अंततः हटाए गए रिकॉर्ड को हटाने के लिए तालिका को फिर से बनाने की आवश्यकता होती है। उपरोक्त विधियाँ O(1) को अद्यतन करने और मौजूदा रिकॉर्ड को हटाने की सुविधा प्रदान करती हैं, साथ ही यदि तालिका आकार का उच्च-जल चिह्न बढ़ता है तो कभी-कभी पुनर्निर्माण भी किया जाता है।
हटाने की एक अन्य तकनीक बस स्लॉट को हटाए गए के रूप में चिह्नित करना है। चूँकि अंततः हटाए गए रिकॉर्ड को हटाने के लिए तालिका को फिर से बनाने की आवश्यकता होती है। उपरोक्त विधियाँ O(1) को अद्यतन करने और उपस्थित रिकॉर्ड को हटाने की सुविधा प्रदान करती हैं, साथ ही यदि तालिका आकार का उच्च-जल चिह्न बढ़ता है तो कभी-कभी पुनर्निर्माण भी किया जाता है।


उपरोक्त O(1) हटाने की विधि केवल सिंगल-स्लॉट स्टेपिंग के साथ रैखिक रूप से जांच की गई हैश तालिकाओं में ही संभव है। ऐसे मामले में जहां एक ऑपरेशन में कई रिकॉर्ड हटाए जाने हैं, हटाने और बाद में पुनर्निर्माण के लिए स्लॉट चिह्नित करना अधिक कुशल हो सकता है।
उपरोक्त O(1) हटाने की विधि केवल सिंगल-स्लॉट स्टेपिंग के साथ रैखिक रूप से जांच की गई हैश तालिकाओं में ही संभव है। ऐसे स्थिति में जहां एक ऑपरेशन में कई रिकॉर्ड हटाए जाने हैं, हटाने और बाद में पुनर्निर्माण के लिए स्लॉट चिह्नित करना अधिक कुशल हो सकता है।


==यह भी देखें==
==यह भी देखें==
* [[आलसी विलोपन]] - खुले पते का उपयोग करके हैश तालिका से हटाने की एक विधि।
* [[आलसी विलोपन]] - विवर्त पते का उपयोग करके हैश तालिका से हटाने की एक विधि है।


==संदर्भ==
==संदर्भ==

Revision as of 16:37, 18 July 2023

हैश टकराव को रैखिक जांच (अंतराल = 1) द्वारा हल किया गया।

विवर्त संबोधन, या क्लोज्ड हैशिंग, हैश टेबल टकराव समाधान की एक विधि है। इस पद्धति के साथ हैश टकराव को जांच करके, या सरणी में वैकल्पिक स्थानों ('जांच अनुक्रम') के माध्यम से खोज कर हल किया जाता है जब तक कि लक्ष्य रिकॉर्ड नहीं मिल जाता है, या अप्रयुक्त सरणी स्लॉट नहीं मिल जाता है, जो निरुपित करता है कि कोई नहीं है तालिका में ऐसी कुंजी.[1] प्रसिद्ध जांच अनुक्रमों में सम्मिलित हैं:

रैखिक जांच
जिसमें जांच के बीच का अंतराल निश्चित होता है — अधिकांशत:1 पर सेट किया जाता है।
द्विघात जांच
जिसमें जांच के बीच का अंतराल द्विघात रूप से बढ़ता है (इसलिए, सूचकांकों को द्विघात फ़ंक्शन द्वारा वर्णित किया जाता है)।
डबल हैशिंग
जिसमें प्रत्येक रिकॉर्ड के लिए जांच के बीच का अंतराल तय किया जाता है किंतु इसकी गणना किसी अन्य हैश फ़ंक्शन द्वारा की जाती है।

इन विधियों के बीच मुख्य व्यापार यह है कि रैखिक जांच में संदर्भ की सबसे अच्छी स्थानीयता होती है, किंतु क्लस्टरिंग के प्रति सबसे अधिक संवेदनशील होती है, जबकि डबल हैशिंग में कैश प्रदर्शन खराब होता है, किंतु वस्तुतः कोई क्लस्टरिंग प्रदर्शित नहीं होती है; दोनों क्षेत्रों में द्विघात जांच बीच में आती है। डबल हैशिंग के लिए अन्य प्रकार की जांच की तुलना में अधिक गणना की भी आवश्यकता हो सकती है।

कुछ खुली एड्रेसिंग विधियाँ, जैसे होप्सकॉच हैशिंग, रॉबिन हुड हैशिंग, लास्ट-आओ-फर्स्ट-पाओ हैशिंग और कुक्कू हैशिंग नई कुंजी के लिए जगह बनाने के लिए उपस्थित कुंजियों को सरणी में इधर-उधर ले जाती हैं। यह जांच पर आधारित विधियों की तुलना में उत्तम अधिकतम खोज समय देता है [2][3][4][5][6]

विवर्त संबोधन हैश टेबल के प्रदर्शन पर एक महत्वपूर्ण प्रभाव लोड कारक है; अर्थात्, उपयोग की जाने वाली सरणी में स्लॉट का अनुपात जैसे-जैसे लोड कारक 100% की ओर बढ़ता है, किसी दी गई कुंजी को खोजने या डालने के लिए आवश्यक जांचों की संख्या नाटकीय रूप से बढ़ जाती है। एक बार जब तालिका पूरी हो जाती है, तो जांच एल्गोरिदम समाप्त होने में भी विफल हो सकता है। अच्छे हैश फ़ंक्शन के साथ भी, लोड कारक सामान्यतः 80% तक सीमित होते हैं। एक खराब हैश फ़ंक्शन महत्वपूर्ण क्लस्टरिंग उत्पन्न करके बहुत कम लोड कारकों पर भी व्यर्थ प्रदर्शन प्रदर्शित कर सकता है, विशेष रूप से सबसे सरल रैखिक एड्रेसिंग विधि के साथ समान्य रूप से अधिकांश विवर्त संबोधन विधियों के साथ विशिष्ट लोड कारक 50% होते हैं, जबकि हैश_टेबल या सेपरेट_चेनिंग समान्यत: 100% तक का उपयोग कर सकते हैं।

उदाहरण छद्मकोड

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

record pair { key, value, occupied flag (initially unset) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]
function find_slot(key)
    i := hash(key) modulo num_slots
    // search until we either find the key, or find an empty slot.
    while (slot[i] is occupied) and (slot[i].key ≠ key)
        i := (i + 1) modulo num_slots
    return i
function lookup(key)
    i := find_slot(key)
    if slot[i] is occupied   // key is in table
        return slot[i].value
    else                     // key is not in table
        return not found
function set(key, value)
    i := find_slot(key)
    if slot[i] is occupied   // we found our key
        slot[i].value = value
        return
    if the table is almost full
        rebuild the table larger (note 1)
        i := find_slot(key)
    mark slot[i] as occupied
    slot[i].key = key
    slot[i].value = value


नोट 1
तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में घातीय वृद्धि करना आम बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।: 
function remove(key)
    i := find_slot(key)
    if slot[i] is unoccupied
        return   // key is not in the table
    mark slot[i] as unoccupied
    j := i
    loop (note 2)
        j := (j + 1) modulo num_slots
        if slot[j] is unoccupied
            exit loop
        k := hash(slot[j].key) modulo num_slots
        // determine if k lies cyclically in (i,j]
        // i ≤ j: |    i..k..j    |
        // i > j: |.k..j     i....| or |....j     i..k.|
        if i ≤ j
            if (i < k) and (k ≤ j)
                continue loop
        else
            if (i < k) or (k ≤ j)
                continue loop
        slot[i] := slot[j]
        mark slot[j] as unoccupied
        i := j


नोट 2
क्लस्टर में सभी रिकॉर्ड के लिए, उनकी प्राकृतिक हैश स्थिति और उनकी वर्तमान स्थिति के बीच कोई रिक्त स्लॉट नहीं होना चाहिए (अन्यथा लुकअप रिकॉर्ड खोजने से पहले ही समाप्त हो जाएगा)। छद्मकोड में इस बिंदु पर, i एक रिक्त स्लॉट है जो क्लस्टर में पश्चात् के रिकॉर्ड के लिए इस गुण को अमान्य कर सकता है। j एक ऐसा अनुवर्ती रिकॉर्ड है। k राव हैश है जहां कोई टकराव न होने पर j पर रिकॉर्ड स्वाभाविक रूप से हैश तालिका में आ जाएगा। यह परीक्षण पूछ रहा है कि क्या j पर रिकॉर्ड क्लस्टर के आवश्यक गुणों के संबंध में अमान्य रूप से स्थित है, क्योंकि अब i रिक्त है।

हटाने की एक अन्य तकनीक बस स्लॉट को हटाए गए के रूप में चिह्नित करना है। चूँकि अंततः हटाए गए रिकॉर्ड को हटाने के लिए तालिका को फिर से बनाने की आवश्यकता होती है। उपरोक्त विधियाँ O(1) को अद्यतन करने और उपस्थित रिकॉर्ड को हटाने की सुविधा प्रदान करती हैं, साथ ही यदि तालिका आकार का उच्च-जल चिह्न बढ़ता है तो कभी-कभी पुनर्निर्माण भी किया जाता है।

उपरोक्त O(1) हटाने की विधि केवल सिंगल-स्लॉट स्टेपिंग के साथ रैखिक रूप से जांच की गई हैश तालिकाओं में ही संभव है। ऐसे स्थिति में जहां एक ऑपरेशन में कई रिकॉर्ड हटाए जाने हैं, हटाने और बाद में पुनर्निर्माण के लिए स्लॉट चिह्नित करना अधिक कुशल हो सकता है।

यह भी देखें

  • आलसी विलोपन - विवर्त पते का उपयोग करके हैश तालिका से हटाने की एक विधि है।

संदर्भ

  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
  2. ↑ 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.
  3. ↑ Steve Heller. "Efficient C/C++ Programming: Smaller, Faster, Better" 2014. p. 33.
  4. ↑ Patricio V. Poblete, Alfredo Viola. "Robin Hood Hashing really has constant average search cost and variance in full tables". 2016.
  5. ↑ 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.
  6. ↑ Paul E. Black, "Robin Hood hashing", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 17 September 2015.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ओपन_एड्रेसिंग&oldid=228038’