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

From Vigyanwiki
(Created page with "{{Short description|Hash collision resolution technique}} Image:HASHTB12.svg|thumb|362px|right|हैश टकराव को रैखिक जांच (अंतरा...")
 
No edit summary
 
(9 intermediate revisions by 4 users not shown)
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.
"The Analysis of a Hashing Scheme by the Diagonal Poisson Transform".
"The Analysis of a Hashing Scheme by the Diagonal Poisson Transform".
Line 33: Line 29:
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>
वर जोड़ी स्लॉट[0], स्लॉट[1], ..., स्लॉट[num_slots - 1]
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


फ़ंक्शन ढूंढें_स्लॉट(कुंजी)
    i := हैश(कुंजी) मॉड्यूलो num_slots
    ''// तब तक खोजें जब तक हमें या तो चाबी न मिल जाए, या कोई खाली स्लॉट न मिल जाए।''
    जबकि (स्लॉट[i] भरा हुआ है) और (स्लॉट[i].कुंजी ≠ कुंजी)
        i := (i + 1) मॉड्यूलो num_slots
    वापसी मैं


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


फ़ंक्शन सेट (कुंजी, मान)
; नोट 1                                                                                                                                                                                                                : टेबल के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना समान्य बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।: <syntaxhighlight>
    मैं := खोज_स्लॉट(कुंजी)
function remove(key)
    यदि स्लॉट[i] पर कब्जा है ''// हमें हमारी कुंजी मिल गई''
    i := find_slot(key)
        स्लॉट[i].मूल्य = मूल्य
    if slot[i] is unoccupied
        वापस करना
        return  // key is not in the table
    यदि तालिका लगभग भरी हुई है
    mark slot[i] as unoccupied
        बड़ी तालिका का पुनर्निर्माण करें ''(नोट 1)''
    j := i
        मैं := खोज_स्लॉट(कुंजी)
    loop (note 2)
    स्लॉट[i] को कब्जे में के रूप में चिह्नित करें
        j := (j + 1) modulo num_slots
    स्लॉट[i].कुंजी = कुंजी
        if slot[j] is unoccupied
    स्लॉट[i].मूल्य = मूल्य
            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>


; नोट 1: तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना आम बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।


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


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


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


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


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:हैशिंग]]

Latest revision as of 12:27, 28 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=229093’