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

From Vigyanwiki
No edit summary
No edit summary
 
(4 intermediate revisions by 3 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 पर सेट किया जाता है।
Line 30: Line 30:
</ref>
</ref>


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


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


निम्नलिखित छद्मकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक विवर्त संबोधन हैश तालिका का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।<syntaxhighlight>
निम्नलिखित स्यूडोकोड रैखिक जांच और एकल-स्लॉट स्टेपिंग के साथ एक ओपन एड्रेसिंग हैश टेबल का कार्यान्वयन है, एक सामान्य दृष्टिकोण जो हैश फ़ंक्शन अच्छा होने पर प्रभावी होता है। प्रत्येक लुकअप, सेट और रिमूव फ़ंक्शंस सरणी स्लॉट का पता लगाने के लिए एक सामान्य आंतरिक फ़ंक्शन फाइंड_स्लॉट का उपयोग करते हैं जिसमें या तो दी गई कुंजी होती है या होनी चाहिए।<syntaxhighlight>
record pair { key, value, occupied flag (initially unset) }
record pair { key, value, occupied flag (initially unset) }
var pair slot[0], slot[1], ..., slot[num_slots - 1]
var pair slot[0], slot[1], ..., slot[num_slots - 1]
Line 73: Line 73:
   
   


; नोट 1                                                                                                                                                                                                                : तालिका के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना समान्य बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।: <syntaxhighlight>
; नोट 1                                                                                                                                                                                                                : टेबल के पुनर्निर्माण के लिए एक बड़े सरणी को आवंटित करने और पुराने सरणी के सभी तत्वों को नए बड़े सरणी में सम्मिलित करने के लिए सेट ऑपरेशन का पुनरावर्ती उपयोग करने की आवश्यकता होती है। सरणी आकार में [[घातीय वृद्धि]] करना समान्य बात है, उदाहरण के लिए पुराने सरणी आकार को दोगुना करना।: <syntaxhighlight>
function remove(key)
function remove(key)
     i := find_slot(key)
     i := find_slot(key)
Line 111: Line 111:
   
   


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