डायनामिक परफेक्ट हैशिंग: Difference between revisions

Revision as of 16:37, 18 July 2023

कंप्यूटर विज्ञान में, डायनेमिक परफेक्ट हैशिंग हैश तालिका डेटा संरचना में हैश टकराव को हल करने के लिए प्रोग्रामिंग तकनीक है।^[1]^[2]^[3] जबकि इसके हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-सघन है,^{[citation needed]} यह तकनीक उन स्थितियों के लिए उपयोगी है जहां तत्वों के बड़े समूह पर तेज़ क्वेरी, सम्मिलन और विलोपन किया जाना चाहिए।

विवरण

स्थैतिक मामला

एफकेएस योजना

इष्टतम स्थैतिक हैशिंग की समस्या को सबसे पहले सामान्यतः फ्रेडमैन, कोमलोस और ज़ेमेरेडी द्वारा हल किया गया था।^[4] उनके 1984 के पेपर में,^[1]वे दो-स्तरीय हैश तालिका योजना का विवरण देते हैं जिसमें (प्रथम-स्तर) हैश तालिका की प्रत्येक बाल्टी अलग दूसरे-स्तरीय हैश तालिका से मेल खाती है। कुंजियाँ दो बार हैश की जाती हैं—पहला हैश मान प्रथम-स्तरीय हैश तालिका में निश्चित बकेट में मैप होता है; दूसरा हैश मान उस बकेट की दूसरी-स्तरीय हैश तालिका में उस प्रविष्टि की स्थिति बताता है। दूसरे स्तर की तालिका के निर्माण पर टकराव-मुक्त (यानी सही हैशिंग) होने की गारंटी है। नतीजतन, लुक-अप लागत बड़ा ओ अंकन|ओ(1) सबसे खराब स्थिति में जटिलता|सबसे खराब स्थिति में होने की गारंटी है।^[2]

स्थैतिक मामले में, हमें कुल के साथ सेट दिया जाता है $x$ प्रविष्टियाँ, प्रत्येक अद्वितीय कुंजी के साथ, समय से पहले। फ़्रेडमैन, कोमलोस और ज़ेमेरेडी आकार के साथ प्रथम-स्तरीय हैश तालिका चुनते हैं $s=2(x-1)$ बाल्टियाँ।^[2]

निर्मित करना, $x$ प्रविष्टियों को अलग किया गया है $s$ शीर्ष-स्तरीय हैशिंग फ़ंक्शन द्वारा बकेट, जहां $s=2(x-1)$ . फिर प्रत्येक बाल्टी के लिए $k$ प्रविष्टियों के साथ, दूसरे स्तर की तालिका आवंटित की जाती है $k^{2}$ स्लॉट्स, और इसके हैश फंकशन को सार्वभौमिक हैश फ़ंक्शन सेट से यादृच्छिक रूप से चुना जाता है ताकि यह टकराव-मुक्त हो (यानी उत्तम हैश फ़ंक्शन) और हैश तालिका के साथ संग्रहीत हो। यदि यादृच्छिक रूप से यूनिवर्सल हैश फ़ंक्शन टकराव के साथ तालिका बनाता है, तो टकराव-मुक्त तालिका की गारंटी होने तक नया हैश फ़ंक्शन यादृच्छिक रूप से चुना जाता है। अंत में, टकराव-मुक्त हैश के साथ, $k$ प्रविष्टियाँ दूसरे स्तर की तालिका में हैश की गई हैं।

का द्विघात आकार $k^{2}$ स्पेस यह सुनिश्चित करता है कि टकराव के साथ बेतरतीब ढंग से तालिका बनाना दुर्लभ और आकार से स्वतंत्र है $k$ , रैखिक परिशोधन निर्माण समय प्रदान करना। हालाँकि प्रत्येक दूसरे स्तर की तालिका में द्विघात स्थान की आवश्यकता होती है, यदि प्रथम स्तर की हैश तालिका में डाली गई कुंजियाँ समान वितरण (अलग) हैं, तो समग्र रूप से संरचना अपेक्षित स्थान लेती है $O(n)$ स्थान, चूंकि बाल्टी का आकार छोटा है और इसकी संभावना अधिक है।^[1]

प्रथम-स्तरीय हैश फ़ंक्शन को विशेष रूप से चुना जाता है, ताकि विशिष्ट सेट के लिए $x$ अद्वितीय कुंजी मान, कुल स्थान $T$ सभी द्वितीय-स्तरीय हैश तालिकाओं द्वारा उपयोग अपेक्षित है $O(n)$ स्थान, और अधिक विशेष रूप से $T<s+4\cdot x$ . फ्रेडमैन, कोमलोस और ज़ेमेरेडी ने दिखाया कि हैश फ़ंक्शंस के सार्वभौमिक हैशिंग परिवार को देखते हुए, उनमें से कम से कम आधे फ़ंक्शंस में वह संपत्ति होती है।^[2]

गतिशील मामला

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

गतिशील मामले में, जब कुंजी को हैश तालिका में डाला जाता है, यदि उसके संबंधित उप-तालिका में उसकी प्रविष्टि पर कब्जा कर लिया जाता है, तो टकराव होता है और उप-तालिका को उसकी नई कुल प्रविष्टि गणना और यादृच्छिक रूप से चयनित हैश फ़ंक्शन के आधार पर फिर से बनाया जाता है। क्योंकि द्वितीय स्तर की तालिका का लोड फैक्टर (हैश तालिका) कम रखा जाता है $1/k$ , पुनर्निर्माण दुर्लभ है, और परिशोधन विश्लेषण सम्मिलन की अपेक्षित लागत है $O(1)$ .^[2]इसी प्रकार, विलोपन की परिशोधित अपेक्षित लागत है $O(1)$ .^[2]

इसके अतिरिक्त, गतिशील मामले में शीर्ष-स्तरीय तालिका या किसी उप-सारणी का अंतिम आकार अज्ञात है। उम्मीद बनाए रखने का तरीका $O(n)$ पर्याप्त संख्या में सम्मिलन और विलोपन होने पर तालिका का स्थान पूर्ण पुनर्निर्माण का संकेत देता है। डाइट्ज़फेलबिंगर एट अल के परिणामों के आधार पर,^[2]जब तक सम्मिलन या विलोपन की कुल संख्या पिछले निर्माण के समय तत्वों की संख्या से अधिक हो जाती है, तब तक सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत बनी रहती है $O(1)$ पूरी पुनर्रचना को ध्यान में रखते हुए।

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

स्यूडोकोड कार्यान्वयन

पता लगाएँ

फ़ंक्शन लोकेट(x) है
    जे := एच(्स)
    यदि (स्थिति एच_j(x) सबटेबल टी का_jx शामिल है (हटाया नहीं गया))
        'वापसी' (x, S में है)
    'अगर अंत'
    'अन्य'
        'वापसी' (x, S में नहीं है)
    'अन्यथा समाप्त'
'अंत'

सम्मिलित करें

j पर नई प्रविष्टि x को सम्मिलित करने के दौरान, वैश्विक संचालन काउंटर, गिनती, बढ़ जाती है।

यदि x, j पर मौजूद है, लेकिन हटाए गए के रूप में चिह्नित है, तो निशान हटा दिया जाता है।

यदि x, j या उपसारणी T पर मौजूद है_j, और हटाए गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि टकराव होता है और जे^वेंबकेट की दूसरी-स्तरीय तालिका टी_j अलग यादृच्छिक रूप से चयनित हैश फ़ंक्शन एच के साथ फिर से बनाया गया है_j.

'फ़ंक्शन' सम्मिलित करें (x) 'है'
    गिनती = गिनती + 1;
    'अगर' (गिनती > एम)
        FullRehash(x);
    'अगर अंत'
    'अन्य'
        जे = एच(्स);
        'अगर' (स्थिति एच_j(x) सबटेबल टी का_jx शामिल है)
            'यदि' (x को हटा दिया गया चिह्नित किया गया है)
                डिलीट मार्कर को हटा दें;
            'अगर अंत'
        'अगर अंत'
        'अन्य'
            बी_j= बी_j+ 1;
            'अगर' (बी_j<= एम_j)
                'अगर' स्थिति एच_j(x) टी का_jखाली है
                    x को स्थिति h में संग्रहित करें_j(x) टी का_j;
                'अगर अंत'
                'अन्य'
                    T के सभी अचिह्नित तत्वों को रखें_jसूची में एल_j;
                    सूची L में x जोड़ें_j;
                    बी_j= L की लंबाई_j;
                    'दोहराना'
                        एच_j= एच में यादृच्छिक रूप से चुना गया फ़ंक्शन_sj;
                    'जब तक' एच_jएल के तत्वों पर विशेषण है_j;
                    सूची एल में शामिल सभी लोगों के लिए_jY को स्थिति h में संग्रहित करें_j(y) टी का_j;
                    'के लिए अंत'
                'अन्यथा समाप्त'
            'अगर अंत'
            'अन्य'
                एम_j= 2 * अधिकतम {1, मी_j};
                एस_j= 2 * मी_j* (एम_j- 1);
                'यदि' सभी एस का कुल योग_j ≤ 32 * एम²/s(M) + 4 * M
                    एस आवंटित करें_jटी के लिए कोशिकाएं_j;
                    T के सभी अचिह्नित तत्वों को रखें_jसूची में एल_j;
                    सूची L में x जोड़ें_j;
                    बी_j= L की लंबाई_j;
                    'दोहराना'
                        एच_j= एच में यादृच्छिक रूप से चुना गया फ़ंक्शन_sj;
                    'जब तक' एच_jएल के तत्वों पर विशेषण है_j;
                    सूची एल में शामिल सभी लोगों के लिए_jY को स्थिति h में संग्रहित करें_j(y) टी का_j;
                    'पहले की तुलना'
                'अगर से'
                'अन्य'
                    FullRehash(x);
                'अन्य की तुलना में'
            'अन्य की तुलना में'
        'अन्य की तुलना में'
    'अन्य की तुलना में'
'बजाय'

हटाएं

x का विलोपन केवल x को हटाए बिना और वेतन वृद्धि की गिनती के रूप में चिह्नित करता है। सम्मिलन और विलोपन दोनों के मामले में, यदि गिनती सीमा एम तक पहुंचती है तो पूरी तालिका फिर से बनाई जाती है, जहां एम नए चरण की शुरुआत में एस के आकार का कुछ स्थिर गुणक है। यहां चरण का तात्पर्य पूर्ण पुनर्निर्माण के बीच के समय से है। ध्यान दें कि यहां Delete(x) में -1 ऐसे तत्व का प्रतिनिधित्व है जो सभी संभावित तत्वों U के सेट में नहीं है।

'फ़ंक्शन' हटाएँ(x) 'है'
    गिनती = गिनती + 1;
    जे = एच(्स);
    'अगर' स्थिति एच_j(x) उपसारणी Tj में x शामिल है
        x को हटाए गए के रूप में चिह्नित करें;
    'अगर अंत'
    'अन्य'
        'वापसी' (x, S का सदस्य नहीं है);
    'अन्यथा समाप्त'
    'अगर' (गिनती >= एम)
        फुलरिहैश(-1);
    'अगर अंत'
'अंत'

पूर्ण पुनर्निर्माण

S की तालिका का पूर्ण पुनर्निर्माण सबसे पहले हटाए गए के रूप में चिह्नित सभी तत्वों को हटाकर शुरू होता है और फिर अगले थ्रेशोल्ड मान M को S के आकार के कुछ स्थिर गुणक पर सेट करता है। हैश फ़ंक्शन, जो S को s(M) उपसमुच्चय में विभाजित करता है, जहां उपसमुच्चय j का आकार s है_j, बार-बार यादृच्छिक रूप से तब तक चुना जाता है जब तक:

$\sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.$ अंत में, प्रत्येक उपसारणी टी के लिए_j हैश फ़ंक्शन एच_jH से बार-बार यादृच्छिक रूप से चुना जाता है_sjजब तक एच_jटी के तत्वों पर विशेषण है_j. आकार n के साथ S की तालिका के पूर्ण पुनर्निर्माण के लिए अपेक्षित समय O(n) है।^[2]

फ़ंक्शन FullRehash(x) है

    T के सभी अचिह्नित तत्वों को L सूची में रखें;
    यदि (x U में है)
        x को L में जोड़ें;
    अगर अंत
    गिनती = सूची की लंबाई एल;
    एम = (1 + सी) * अधिकतम{गिनती, 4};
    दोहराना
        h = H में यादृच्छिक रूप से चुना गया फ़ंक्शन_s(M);
        'सभी के लिए' j < s(M)
             सूची बनाएं एल_jh(x) = j के लिए;
            बी_j= L की लंबाई_j;
            एम_j= 2 * बी_j;
            एस_j= 2 * मी_j* (एम_j- 1);
        'के लिए अंत'
    'जब तक' सभी का योग न हो जाए_j ≤ 32 * एम²/s(M) + 4 * M
    'सभी के लिए' j < s(M)
        स्थान आवंटित करें_jसबटेबल टी के लिए_j;
        'दोहराना'
            एच_j= एच में यादृच्छिक रूप से चुना गया फ़ंक्शन_sj;
        'जब तक' एच_jसूची एल के तत्वों पर विशेषण है_j;
    'के लिए अंत'
    सूची एल पर सभी ्स के लिए 'के लिए'_jx को स्थिति h में संग्रहित करें_j(x) टी का_j;
    'के लिए अंत'
'अंत'

यह भी देखें

उत्तम हैशिंग

संदर्भ

↑ ^1.0 ^1.1 ^1.2 Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. "Dynamic Perfect Hashing: Upper and Lower Bounds" Archived 2016-03-04 at the Wayback Machine. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094
↑ Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.
↑ Yap, Chee. "एफकेएस योजना के लिए सार्वभौमिक निर्माण". New York University. New York University. Retrieved 15 February 2015.^{[permanent dead link]}

[inventor-1] 1.0 ^1.1 ^1.2 Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#

[dietzfelbinger-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. "Dynamic Perfect Hashing: Upper and Lower Bounds" Archived 2016-03-04 at the Wayback Machine. SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi:10.1137/S0097539791194094

[3] Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.

[4] Yap, Chee. "एफकेएस योजना के लिए सार्वभौमिक निर्माण". New York University. New York University. Retrieved 15 February 2015.^{[permanent dead link]}

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{Short description|Programming technique for resolving duplicate hash values in a hash table data structure}}
-[[कंप्यूटर विज्ञान]] में, डायनेमिक परफेक्ट हैशिंग [[ हैश तालिका ]] [[डेटा संरचना]] में हैश टकराव को हल करने के लिए एक प्रोग्रामिंग तकनीक है।<ref name="inventor">Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
+[[कंप्यूटर विज्ञान]] में, डायनेमिक परफेक्ट हैशिंग [[ हैश तालिका ]] [[डेटा संरचना]] में हैश टकराव को हल करने के लिए  प्रोग्रामिंग तकनीक है।<ref name="inventor">Fredman, M. L., Komlós, J., and Szemerédi, E. 1984. Storing a Sparse Table with 0(1) Worst Case Access Time. J. ACM 31, 3 (Jun. 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
 [http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf "Dynamic Perfect Hashing: Upper and Lower Bounds"] {{Webarchive|url=https://web.archive.org/web/20160304094014/http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf |date=2016-03-04 }}.
 SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
@@ Line 9: / Line 9: @@
 MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.
 </ref>
-जबकि इसके हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-सघन है,{{citation needed|date=April 2015}} यह तकनीक उन स्थितियों के लिए उपयोगी है जहां तत्वों के एक बड़े समूह पर तेज़ क्वेरी, सम्मिलन और विलोपन किया जाना चाहिए।
+जबकि इसके हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-सघन है,{{citation needed|date=April 2015}} यह तकनीक उन स्थितियों के लिए उपयोगी है जहां तत्वों के  बड़े समूह पर तेज़ क्वेरी, सम्मिलन और विलोपन किया जाना चाहिए।
 ==विवरण==
@@ Line 18: / Line 18: @@
 {{main | static hashing#FKS Hashing }}
-इष्टतम [[स्थैतिक हैशिंग]] की समस्या को सबसे पहले सामान्यतः फ्रेडमैन, कोमलोस और ज़ेमेरेडी द्वारा हल किया गया था।<ref>{{cite web|last1=Yap|first1=Chee|title=एफकेएस योजना के लिए सार्वभौमिक निर्माण|url=ftp://cs.nyu.edu/pub/local/yap/cg/hashFKS.ps.gz|website=New York University|publisher=New York University|accessdate=15 February 2015}}{{dead link|date=September 2017 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> उनके 1984 के पेपर में,<ref name="inventor"/>वे एक दो-स्तरीय हैश तालिका योजना का विवरण देते हैं जिसमें (प्रथम-स्तर) हैश तालिका की प्रत्येक बाल्टी एक अलग दूसरे-स्तरीय हैश तालिका से मेल खाती है। कुंजियाँ दो बार हैश की जाती हैं—पहला हैश मान प्रथम-स्तरीय हैश तालिका में एक निश्चित बकेट में मैप होता है; दूसरा हैश मान उस बकेट की दूसरी-स्तरीय हैश तालिका में उस प्रविष्टि की स्थिति बताता है। दूसरे स्तर की तालिका के निर्माण पर टकराव-मुक्त (यानी सही हैशिंग) होने की गारंटी है। नतीजतन, लुक-अप लागत [[बड़ा ओ अंकन]]|ओ(1) सबसे खराब स्थिति में जटिलता|सबसे खराब स्थिति में होने की गारंटी है।<ref name="dietzfelbinger"/>
+इष्टतम [[स्थैतिक हैशिंग]] की समस्या को सबसे पहले सामान्यतः फ्रेडमैन, कोमलोस और ज़ेमेरेडी द्वारा हल किया गया था।<ref>{{cite web|last1=Yap|first1=Chee|title=एफकेएस योजना के लिए सार्वभौमिक निर्माण|url=ftp://cs.nyu.edu/pub/local/yap/cg/hashFKS.ps.gz|website=New York University|publisher=New York University|accessdate=15 February 2015}}{{dead link|date=September 2017 |bot=InternetArchiveBot |fix-attempted=yes }}</ref> उनके 1984 के पेपर में,<ref name="inventor"/>वे  दो-स्तरीय हैश तालिका योजना का विवरण देते हैं जिसमें (प्रथम-स्तर) हैश तालिका की प्रत्येक बाल्टी  अलग दूसरे-स्तरीय हैश तालिका से मेल खाती है। कुंजियाँ दो बार हैश की जाती हैं—पहला हैश मान प्रथम-स्तरीय हैश तालिका में  निश्चित बकेट में मैप होता है; दूसरा हैश मान उस बकेट की दूसरी-स्तरीय हैश तालिका में उस प्रविष्टि की स्थिति बताता है। दूसरे स्तर की तालिका के निर्माण पर टकराव-मुक्त (यानी सही हैशिंग) होने की गारंटी है। नतीजतन, लुक-अप लागत [[बड़ा ओ अंकन]]|ओ(1) सबसे खराब स्थिति में जटिलता|सबसे खराब स्थिति में होने की गारंटी है।<ref name="dietzfelbinger"/>
-स्थैतिक मामले में, हमें कुल के साथ एक सेट दिया जाता है {{mvar|x}} प्रविष्टियाँ, प्रत्येक एक अद्वितीय कुंजी के साथ, समय से पहले।
+स्थैतिक मामले में, हमें कुल के साथ  सेट दिया जाता है {{mvar|x}} प्रविष्टियाँ, प्रत्येक  अद्वितीय कुंजी के साथ, समय से पहले।
 फ़्रेडमैन, कोमलोस और ज़ेमेरेडी आकार के साथ प्रथम-स्तरीय हैश तालिका चुनते हैं <math>s = 2(x-1)</math> बाल्टियाँ।<ref name="dietzfelbinger"/>
-निर्मित करना, {{mvar|x}} प्रविष्टियों को अलग किया गया है {{mvar|s}} शीर्ष-स्तरीय हैशिंग फ़ंक्शन द्वारा बकेट, जहां <math>s = 2(x-1)</math>. फिर प्रत्येक बाल्टी के लिए {{mvar|k}} प्रविष्टियों के साथ, एक दूसरे स्तर की तालिका आवंटित की जाती है <math>k^2</math> स्लॉट्स, और इसके [[हैश फंकशन]] को सार्वभौमिक हैश फ़ंक्शन सेट से यादृच्छिक रूप से चुना जाता है ताकि यह टकराव-मुक्त हो (यानी एक [[उत्तम हैश फ़ंक्शन]]) और हैश तालिका के साथ संग्रहीत हो। यदि यादृच्छिक रूप से [[यूनिवर्सल हैश फ़ंक्शन]] टकराव के साथ एक तालिका बनाता है, तो टकराव-मुक्त तालिका की गारंटी होने तक एक नया हैश फ़ंक्शन यादृच्छिक रूप से चुना जाता है। अंत में, टकराव-मुक्त हैश के साथ, {{mvar|k}} प्रविष्टियाँ दूसरे स्तर की तालिका में हैश की गई हैं।
+निर्मित करना, {{mvar|x}} प्रविष्टियों को अलग किया गया है {{mvar|s}} शीर्ष-स्तरीय हैशिंग फ़ंक्शन द्वारा बकेट, जहां <math>s = 2(x-1)</math>. फिर प्रत्येक बाल्टी के लिए {{mvar|k}} प्रविष्टियों के साथ,  दूसरे स्तर की तालिका आवंटित की जाती है <math>k^2</math> स्लॉट्स, और इसके [[हैश फंकशन]] को सार्वभौमिक हैश फ़ंक्शन सेट से यादृच्छिक रूप से चुना जाता है ताकि यह टकराव-मुक्त हो (यानी  [[उत्तम हैश फ़ंक्शन]]) और हैश तालिका के साथ संग्रहीत हो। यदि यादृच्छिक रूप से [[यूनिवर्सल हैश फ़ंक्शन]] टकराव के साथ  तालिका बनाता है, तो टकराव-मुक्त तालिका की गारंटी होने तक  नया हैश फ़ंक्शन यादृच्छिक रूप से चुना जाता है। अंत में, टकराव-मुक्त हैश के साथ, {{mvar|k}} प्रविष्टियाँ दूसरे स्तर की तालिका में हैश की गई हैं।
-का द्विघात आकार <math>k^2</math> स्पेस यह सुनिश्चित करता है कि टकराव के साथ बेतरतीब ढंग से एक तालिका बनाना दुर्लभ और आकार से स्वतंत्र है {{mvar|k}}, रैखिक परिशोधन निर्माण समय प्रदान करना। हालाँकि प्रत्येक दूसरे स्तर की तालिका में द्विघात स्थान की आवश्यकता होती है, यदि प्रथम स्तर की हैश तालिका में डाली गई कुंजियाँ [[समान वितरण (अलग)]] हैं, तो समग्र रूप से संरचना अपेक्षित स्थान लेती है <math>O(n)</math> स्थान, चूंकि बाल्टी का आकार छोटा है और इसकी [[संभावना]] अधिक है।<ref name="inventor"/>
+का द्विघात आकार <math>k^2</math> स्पेस यह सुनिश्चित करता है कि टकराव के साथ बेतरतीब ढंग से  तालिका बनाना दुर्लभ और आकार से स्वतंत्र है {{mvar|k}}, रैखिक परिशोधन निर्माण समय प्रदान करना। हालाँकि प्रत्येक दूसरे स्तर की तालिका में द्विघात स्थान की आवश्यकता होती है, यदि प्रथम स्तर की हैश तालिका में डाली गई कुंजियाँ [[समान वितरण (अलग)]] हैं, तो समग्र रूप से संरचना अपेक्षित स्थान लेती है <math>O(n)</math> स्थान, चूंकि बाल्टी का आकार छोटा है और इसकी [[संभावना]] अधिक है।<ref name="inventor"/>
 प्रथम-स्तरीय हैश फ़ंक्शन को विशेष रूप से चुना जाता है, ताकि विशिष्ट सेट के लिए {{mvar|x}} अद्वितीय कुंजी मान, कुल स्थान {{mvar|T}} सभी द्वितीय-स्तरीय हैश तालिकाओं द्वारा उपयोग अपेक्षित है <math>O(n)</math> स्थान, और अधिक विशेष रूप से <math>T < s + 4 \cdot x</math>.
-फ्रेडमैन, कोमलोस और ज़ेमेरेडी ने दिखाया कि हैश फ़ंक्शंस के एक [[सार्वभौमिक हैशिंग]] परिवार को देखते हुए, उनमें से कम से कम आधे फ़ंक्शंस में वह संपत्ति होती है।<ref name="dietzfelbinger"/>
+फ्रेडमैन, कोमलोस और ज़ेमेरेडी ने दिखाया कि हैश फ़ंक्शंस के  [[सार्वभौमिक हैशिंग]] परिवार को देखते हुए, उनमें से कम से कम आधे फ़ंक्शंस में वह संपत्ति होती है।<ref name="dietzfelbinger"/>
+'''गतिशील मामला'''
-===गतिशील मामला===
+डिट्ज़फेलबिंगर एट अल।  गतिशील शब्दकोश एल्गोरिथ्म प्रस्तुत करें, जब n आइटमों का  सेट शब्दकोष में क्रमिक रूप से जोड़ा जाता है, तो सदस्यता क्वेरी हमेशा निरंतर समय में चलती हैं और इसलिए <math>O(1)</math> सबसे खराब स्थिति में, आवश्यक कुल भंडारण है <math>O(n)</math> (रैखिक), और <math>O(1)</math> अपेक्षित परिशोधन सम्मिलन और विलोपन समय (परिशोधन स्थिर समय)।
-डिट्ज़फेलबिंगर एट अल। एक गतिशील शब्दकोश एल्गोरिथ्म प्रस्तुत करें, जब n आइटमों का एक सेट शब्दकोष में क्रमिक रूप से जोड़ा जाता है, तो सदस्यता क्वेरी हमेशा निरंतर समय में चलती हैं और इसलिए <math>O(1)</math> सबसे खराब स्थिति में, आवश्यक कुल भंडारण है <math>O(n)</math> (रैखिक), और <math>O(1)</math> अपेक्षित परिशोधन सम्मिलन और विलोपन समय (परिशोधन स्थिर समय)।
+गतिशील मामले में, जब  कुंजी को हैश तालिका में डाला जाता है, यदि उसके संबंधित उप-तालिका में उसकी प्रविष्टि पर कब्जा कर लिया जाता है, तो टकराव होता है और उप-तालिका को उसकी नई कुल प्रविष्टि गणना और यादृच्छिक रूप से चयनित हैश फ़ंक्शन के आधार पर फिर से बनाया जाता है। क्योंकि द्वितीय स्तर की तालिका का लोड फैक्टर (हैश तालिका) कम रखा जाता है <math>1/k</math>, पुनर्निर्माण दुर्लभ है, और [[परिशोधन विश्लेषण]] सम्मिलन की अपेक्षित लागत है <math>O(1)</math>.<ref name="dietzfelbinger"/>इसी प्रकार, विलोपन की परिशोधित अपेक्षित लागत है <math>O(1)</math>.<ref name="dietzfelbinger"/>
-गतिशील मामले में, जब एक कुंजी को हैश तालिका में डाला जाता है, यदि उसके संबंधित उप-तालिका में उसकी प्रविष्टि पर कब्जा कर लिया जाता है, तो टकराव होता है और उप-तालिका को उसकी नई कुल प्रविष्टि गणना और यादृच्छिक रूप से चयनित हैश फ़ंक्शन के आधार पर फिर से बनाया जाता है। क्योंकि द्वितीय स्तर की तालिका का लोड फैक्टर (हैश तालिका) कम रखा जाता है <math>1/k</math>, पुनर्निर्माण दुर्लभ है, और [[परिशोधन विश्लेषण]] सम्मिलन की अपेक्षित लागत है <math>O(1)</math>.<ref name="dietzfelbinger"/>इसी प्रकार, विलोपन की परिशोधित अपेक्षित लागत है <math>O(1)</math>.<ref name="dietzfelbinger"/>
+इसके अतिरिक्त, गतिशील मामले में शीर्ष-स्तरीय तालिका या किसी उप-सारणी का अंतिम आकार अज्ञात है। उम्मीद बनाए रखने का  तरीका <math>O(n)</math> पर्याप्त संख्या में सम्मिलन और विलोपन होने पर तालिका का स्थान पूर्ण पुनर्निर्माण का संकेत देता है। डाइट्ज़फेलबिंगर एट अल के परिणामों के आधार पर,<ref name="dietzfelbinger"/>जब तक सम्मिलन या विलोपन की कुल संख्या पिछले निर्माण के समय तत्वों की संख्या से अधिक हो जाती है, तब तक सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत बनी रहती है <math>O(1)</math> पूरी पुनर्रचना को ध्यान में रखते हुए।
-इसके अतिरिक्त, गतिशील मामले में शीर्ष-स्तरीय तालिका या किसी उप-सारणी का अंतिम आकार अज्ञात है। उम्मीद बनाए रखने का एक तरीका <math>O(n)</math> पर्याप्त संख्या में सम्मिलन और विलोपन होने पर तालिका का स्थान पूर्ण पुनर्निर्माण का संकेत देता है। डाइट्ज़फेलबिंगर एट अल के परिणामों के आधार पर,<ref name="dietzfelbinger"/>जब तक सम्मिलन या विलोपन की कुल संख्या पिछले निर्माण के समय तत्वों की संख्या से अधिक हो जाती है, तब तक सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत बनी रहती है <math>O(1)</math> पूरी पुनर्रचना को ध्यान में रखते हुए।
 डाइट्ज़फेलबिंगर एट अल द्वारा डायनामिक परफेक्ट हैशिंग का कार्यान्वयन। इन अवधारणाओं का उपयोग करता है, साथ ही [[आलसी विलोपन]] भी करता है, और नीचे छद्म कोड में दिखाया गया है।
@@ Line 46: / Line 45: @@
   फ़ंक्शन लोकेट(''x'') है
-      ''जे'' := एच(एक्स)
+      ''जे'' := एच(्स)
       यदि (स्थिति एच<sub>j</sub>(x) सबटेबल टी का<sub>j</sub>x शामिल है (हटाया नहीं गया))
           'वापसी' (x, S में है)
@@ Line 57: / Line 56: @@
 === सम्मिलित करें ===
-j पर एक नई प्रविष्टि x को सम्मिलित करने के दौरान, वैश्विक संचालन काउंटर, गिनती, बढ़ जाती है।
+j पर  नई प्रविष्टि x को सम्मिलित करने के दौरान, वैश्विक संचालन काउंटर, गिनती, बढ़ जाती है।
 यदि x, j पर मौजूद है, लेकिन हटाए गए के रूप में चिह्नित है, तो निशान हटा दिया जाता है।
-यदि x, j या उपसारणी T पर मौजूद है<sub>j</sub>, और हटाए गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि टकराव होता है और जे<sup>वें</sup>बकेट की दूसरी-स्तरीय तालिका टी<sub>j</sub>एक अलग यादृच्छिक रूप से चयनित हैश फ़ंक्शन एच के साथ फिर से बनाया गया है<sub>j</sub>.
+यदि x, j या उपसारणी T पर मौजूद है<sub>j</sub>, और हटाए गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि टकराव होता है और जे<sup>वें</sup>बकेट की दूसरी-स्तरीय तालिका टी<sub>j</sub> अलग यादृच्छिक रूप से चयनित हैश फ़ंक्शन एच के साथ फिर से बनाया गया है<sub>j</sub>.
   'फ़ंक्शन' सम्मिलित करें (x) 'है'
@@ Line 69: / Line 68: @@
       'अगर अंत'
       'अन्य'
-          जे = एच(एक्स);
+          जे = एच(्स);
           'अगर' (स्थिति एच<sub>''j''</sub>(x) सबटेबल टी का<sub>j</sub>x शामिल है)
               'यदि' (x को हटा दिया गया चिह्नित किया गया है)
@@ Line 116: / Line 115: @@
 === हटाएं ===
-x का विलोपन केवल x को हटाए बिना और वेतन वृद्धि की गिनती के रूप में चिह्नित करता है। सम्मिलन और विलोपन दोनों के मामले में, यदि गिनती सीमा एम तक पहुंचती है तो पूरी तालिका फिर से बनाई जाती है, जहां एम एक नए चरण की शुरुआत में एस के आकार का कुछ स्थिर गुणक है। यहां चरण का तात्पर्य पूर्ण पुनर्निर्माण के बीच के समय से है। ध्यान दें कि यहां Delete(x) में -1 एक ऐसे तत्व का प्रतिनिधित्व है जो सभी संभावित तत्वों U के सेट में नहीं है।
+x का विलोपन केवल x को हटाए बिना और वेतन वृद्धि की गिनती के रूप में चिह्नित करता है। सम्मिलन और विलोपन दोनों के मामले में, यदि गिनती सीमा एम तक पहुंचती है तो पूरी तालिका फिर से बनाई जाती है, जहां एम  नए चरण की शुरुआत में एस के आकार का कुछ स्थिर गुणक है। यहां चरण का तात्पर्य पूर्ण पुनर्निर्माण के बीच के समय से है। ध्यान दें कि यहां Delete(x) में -1  ऐसे तत्व का प्रतिनिधित्व है जो सभी संभावित तत्वों U के सेट में नहीं है।
   'फ़ंक्शन' हटाएँ(x) 'है'
       गिनती = गिनती + 1;
-      जे = एच(एक्स);
+      जे = एच(्स);
       'अगर' स्थिति एच<sub>j</sub>(x) उपसारणी Tj में x शामिल है
           x को हटाए गए के रूप में चिह्नित करें;
@@ Line 134: / Line 133: @@
 === पूर्ण पुनर्निर्माण ===
-S की तालिका का पूर्ण पुनर्निर्माण सबसे पहले हटाए गए के रूप में चिह्नित सभी तत्वों को हटाकर शुरू होता है और फिर अगले थ्रेशोल्ड मान M को S के आकार के कुछ स्थिर गुणक पर सेट करता है। एक हैश फ़ंक्शन, जो S को s(M) उपसमुच्चय में विभाजित करता है, जहां उपसमुच्चय j का आकार s है<sub>j</sub>, बार-बार यादृच्छिक रूप से तब तक चुना जाता है जब तक:
+S की तालिका का पूर्ण पुनर्निर्माण सबसे पहले हटाए गए के रूप में चिह्नित सभी तत्वों को हटाकर शुरू होता है और फिर अगले थ्रेशोल्ड मान M को S के आकार के कुछ स्थिर गुणक पर सेट करता है।  हैश फ़ंक्शन, जो S को s(M) उपसमुच्चय में विभाजित करता है, जहां उपसमुच्चय j का आकार s है<sub>j</sub>, बार-बार यादृच्छिक रूप से तब तक चुना जाता है जब तक:
 <math>\sum_{0\le j\le s(M)} s_j \le \frac{32M^2}{s(M)} + 4M.</math>
-अंत में, प्रत्येक उपसारणी टी के लिए<sub>j</sub>एक हैश फ़ंक्शन एच<sub>j</sub>H से बार-बार यादृच्छिक रूप से चुना जाता है<sub>sj</sub>जब तक एच<sub>j</sub>टी के तत्वों पर विशेषण है<sub>j</sub>. आकार n के साथ S की तालिका के पूर्ण पुनर्निर्माण के लिए अपेक्षित समय O(n) है।<ref name="dietzfelbinger"/>
+अंत में, प्रत्येक उपसारणी टी के लिए<sub>j</sub> हैश फ़ंक्शन एच<sub>j</sub>H से बार-बार यादृच्छिक रूप से चुना जाता है<sub>sj</sub>जब तक एच<sub>j</sub>टी के तत्वों पर विशेषण है<sub>j</sub>. आकार n के साथ S की तालिका के पूर्ण पुनर्निर्माण के लिए अपेक्षित समय O(n) है।<ref name="dietzfelbinger"/>
 फ़ंक्शन FullRehash(''x'') है
@@ Line 149: / Line 148: @@
           h = ''H'' में यादृच्छिक रूप से चुना गया फ़ंक्शन<sub>s(M)</sub>;
           'सभी के लिए' j < s(M)
-             एक सूची बनाएं एल<sub>j</sub>h(x) = j के लिए;
+              सूची बनाएं एल<sub>j</sub>h(x) = j के लिए;
               बी<sub>j</sub>= L की लंबाई<sub>j</sub>;
               एम<sub>j</sub>= 2 * बी<sub>j</sub>;
@@ Line 161: / Line 160: @@
           'जब तक' एच<sub>j</sub>सूची एल के तत्वों पर विशेषण है<sub>j</sub>;
       'के लिए अंत'
-      सूची एल पर सभी एक्स के लिए 'के लिए'<sub>j</sub>x को स्थिति h में संग्रहित करें<sub>''j''</sub>(x) टी का<sub>j</sub>;
+      सूची एल पर सभी ्स के लिए 'के लिए'<sub>j</sub>x को स्थिति h में संग्रहित करें<sub>''j''</sub>(x) टी का<sub>j</sub>;
       'के लिए अंत'
   'अंत'

Anonymous

Search

डायनामिक परफेक्ट हैशिंग: Difference between revisions

Namespaces

More

Page actions

Revision as of 16:37, 18 July 2023

Contents

विवरण

स्थैतिक मामला

एफकेएस योजना

स्यूडोकोड कार्यान्वयन

पता लगाएँ

सम्मिलित करें

हटाएं

पूर्ण पुनर्निर्माण

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डायनामिक परफेक्ट हैशिंग: Difference between revisions

Revision as of 16:37, 18 July 2023

विवरण

स्थैतिक मामला

एफकेएस योजना

स्यूडोकोड कार्यान्वयन

पता लगाएँ

सम्मिलित करें

हटाएं

पूर्ण पुनर्निर्माण

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories