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

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

विवरण

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

एफकेएस योजना

Main article: static hashing § FKS Hashing

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

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

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

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

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

गतिशील मामला

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

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

इसके अतिरिक्त, गतिशील मामले में शीर्ष-स्तरीय तालिका या किसी उप-सारणी का अंतिम आकार अज्ञात है। उम्मीद बनाए रखने का एक तरीका $O(n)$ पर्याप्त संख्या में सम्मिलन और विलोपन होने पर तालिका का स्थान पूर्ण पुनर्निर्माण का संकेत देता है। डाइट्ज़फेलबिंगर एट अल के परिणामों के आधार पर,जब तक सम्मिलन या विलोपन की कुल संख्या पिछले निर्माण के समय तत्वों की संख्या से अधिक हो जाती है, तब तक सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत बनी रहती है $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 * एम2/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) है।

फ़ंक्शन 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 * एम2/s(M) + 4 * M
    'सभी के लिए' j < s(M)
        स्थान आवंटित करेंjसबटेबल टी के लिएj;
        'दोहराना'
            एचj= एच में यादृच्छिक रूप से चुना गया फ़ंक्शनsj;
        'जब तक' एचjसूची एल के तत्वों पर विशेषण हैj;
    'के लिए अंत'
    सूची एल पर सभी एक्स के लिए 'के लिए'jx को स्थिति h में संग्रहित करेंj(x) टी काj;
    'के लिए अंत'
'अंत'

यह भी देखें

• उत्तम हैशिंग