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

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

विवरण

स्थैतिक केस

एफकेएस योजना

Main article: स्टेटिक हैशिंग § एफकेएस हैशिंग

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

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

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

लोकेट

function Locate(x) is
    j := h(x)
     if (position hj(x) of subtable Tj contains x (not deleted))
        return (x is in S)
     end if
     else 
        return (x is not in S)
   end else
end

इन्सर्ट

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

यदि x, j पर उपस्थित है, किन्तु विस्थापित किये गए के रूप में चिह्नित है, तो प्रतीक विस्थापित कर दिया जाता है।

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

function Insert(x) is
   count = count + 1;
     if (count > M) 
         FullRehash(x);
     end if
    else
        j = h(x);
        if (Position hj(x) of subtable Tj contains x)
            if (x is marked deleted) 
                remove the delete marker;
            end if
        end if
          else
            bj = bj + 1;
            if (bj <= mj) 
                if position hj(x) of Tj is empty 
                    store x in position hj(x) of Tj;
                end if
                else
                     Put all unmarked elements of Tj in list Lj;
                    Append x to list Lj;
                     bj = length of Lj;
                    repeat 
                        hj = randomly chosen function in Hsj;
                    until hj is injective on the elements of Lj;
                    for all y on list Lj
                    store y in position hj(y) of Tj;
                end for
            end else
             end if else
                mj = 2 * max{1, mj};
                sj = 2 * mj * (mj - 1);
                if the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M 
                    Allocate sj cells for Tj;
                     Put all unmarked elements of Tj in list Lj;
                    Append x to list Lj;
                    bj = length of Lj;
                    repeat 
                        hj = randomly chosen function in Hsj;
                    until hj is injective on the elements of Lj;
                    for all y on list Lj
                    store y in position hj(y) of Tj;
                 end for
                end if

                 else
                    FullRehash(x);
                end else
             end else
        end else
     end else
end

डिलीट

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

function Delete(x) is
   count = count + 1;

   j = h(x);
    if position hj(x) of subtable Tj contains x
        mark x as deleted;
    end if
    else 
        return (x is not a member of S);
    end else
    if (count >= M)
        FullRehash(-1);
   end if
end

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

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.$

अंत में, प्रत्येक उपसारणी T_j के लिए हैश फ़ंक्शन H_j को H_sj से बार-बार यादृच्छिक रूप से चयन किया जाता है जब तक h_j ,T_j के तत्वों पर प्रवेश न हो जाए। आकार n के साथ S की टेबल के पूर्ण पुनर्निर्माण के लिए अपेक्षित समय O(n) है।

    function FullRehash(x) is
    Put all unmarked elements of T in list L;
        if (x is in U) 
    append x to L;
    end if
     count = length of list L;
    M = (1 + c) * max{count, 4};
        repeat 
        h = randomly chosen function in Hs(M);
             for all j < s(M) 
            form a list Lj for h(x) = j;
             bj = length of Lj; 
           mj = 2 * bj; 
        sj = 2 * mj * (mj - 1);
     end for
    until the sum total of all sj ≤ 32 * M2 / s(M) + 4 * M
        for all j < s(M) 
        Allocate space sj for subtable Tj;
             repeat 
         hj = randomly chosen function in Hsj;
    until hj is injective on the elements of list Lj;
    end for
    for all x on list Lj 
store x in position hj(x) of Tj;

end for

end

यह भी देखें

• परफेक्ट हैशिंग