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

From Vigyanwiki
(Created page with "{{Short description|Programming technique for resolving duplicate hash values in a hash table data structure}} कंप्यूटर विज्ञान में,...")
 
No edit summary
 
(14 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Programming technique for resolving duplicate hash values in a hash table data structure}}
{{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 }}.
[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.
SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
Line 8: Line 8:
[http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf 6.897: Advanced Data Structures].
[http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf 6.897: Advanced Data Structures].
MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.
MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003.
</ref>
</ref>जबकि इसके हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-इंटेंसिव है, यह तकनीक उन केस के लिए उपयोगी है जहां एलिमेंट्स के बड़े समूह पर फ़ास्ट क्वेरी, इनसेरशंस और डिलीटेशन किया जाना चाहिए।
जबकि इसके हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-सघन है,{{citation needed|date=April 2015}} यह तकनीक उन स्थितियों के लिए उपयोगी है जहां तत्वों के एक बड़े समूह पर तेज़ क्वेरी, सम्मिलन और विलोपन किया जाना चाहिए।


==विवरण==
==विवरण==


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


====एफकेएस योजना====
====एफकेएस योजना====
{{main | static hashing#FKS Hashing }}
{{main |स्टेटिक हैशिंग#एफकेएस हैशिंग}}


इष्टतम [[स्थैतिक हैशिंग]] की समस्या को सबसे पहले सामान्यतः फ्रेडमैन, कोमलोस और ज़ेमेरेडी द्वारा हल किया गया था।<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"/>वे दो-स्तरीय हैश टेबल योजना का विवरण देते हैं जिसमें (प्रथम-स्तर) हैश टेबल की प्रत्येक बकेट विभिन्न दूसरे-स्तरीय हैश टेबल से युग्मित होती है। कीस दो बार हैश की जाती हैं—प्रथम हैश मान प्रथम-स्तरीय हैश टेबल में निश्चित बकेट में मैप होता है; दूसरा हैश मान उस बकेट की दूसरी-स्तरीय हैश टेबल में उस प्रविष्टि की केस बताता है। दूसरे स्तर की टेबल के निर्माण पर कलिसिएंस-फ्री (अर्थात सही हैशिंग) होने का आश्वासन है। परिणाम स्वरुप, सबसे व्यर्थ केस में लुक-अप कास्ट [[बड़ा ओ अंकन|O(1)]] होने का आश्वासन है।<ref name="dietzfelbinger"/>


स्थैतिक मामले में, हमें कुल के साथ एक सेट दिया जाता है {{mvar|x}} प्रविष्टियाँ, प्रत्येक एक अद्वितीय कुंजी के साथ, समय से पहले।
स्थैतिक केस में, हमें समय से पहले, कुल {{mvar|x}} प्रविष्टियों के साथ सेट दिया जाता है, प्रत्येक में अद्वितीय की होती है। फ़्रेडमैन, कोमलोस और ज़ेमेरेडी आकार के साथ प्रथम-स्तरीय हैश टेबल का चयन <math>s = 2(x-1)</math> करते हैं।<ref name="dietzfelbinger"/>
फ़्रेडमैन, कोमलोस और ज़ेमेरेडी आकार के साथ प्रथम-स्तरीय हैश तालिका चुनते हैं <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>.
प्रथम-स्तरीय हैश फ़ंक्शन को विशेष रूप से चयन किया जाता है, जिससे {{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"/>इसी प्रकार, डिलीटेशन का परिशोधित अपेक्षित कास्ट है।<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> पूरी पुनर्रचना को ध्यान में रखते हुए।
डाइट्ज़फेलबिंगर एट अल द्वारा डायनामिक परफेक्ट हैशिंग का कार्यान्वयन है। इन अवधारणाओं का उपयोग करता है, साथ ही [[आलसी विलोपन|लेज़ी डिलीटेशन]] भी करता है, और नीचे सूडो कोड में दिखाया गया है।


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


==स्यूडोकोड कार्यान्वयन==
=== लोकेट ===


=== पता लगाएँ ===
'''function''' Locate(''x'') '''is'''
    ''j'' := h('''x''')
      '''if''' (position h<sub>j</sub>(''x'') of subtable ''T<sub>j</sub>'' contains ''x'' (not deleted))
        '''return''' (''x'' is in ''S'')
      '''end if'''
      '''else'''
        '''return''' (''x'' is not in ''S'')
    '''end else'''
'''end'''


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


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


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


यदि x, j पर मौजूद है, लेकिन हटाए गए के रूप में चिह्नित है, तो निशान हटा दिया जाता है।
यदि x, j या सबटेबल T<sub>j</sub> पर उपस्थित है, और विस्थापित किये गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि कलिसिएंस होता है और ''j''<sup>th</sup> बकेट की दूसरी-स्तरीय टेबल T<sub>j</sub> को भिन्न यादृच्छिक रूप से चयनित हैश फ़ंक्शन ''h<sub>j</sub>'' के साथ फिर से बनाया गया है।


यदि x, j या उपसारणी T पर मौजूद है<sub>j</sub>, और हटाए गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि टकराव होता है और जे<sup>वें</sup>बकेट की दूसरी-स्तरीय तालिका टी<sub>j</sub>एक अलग यादृच्छिक रूप से चयनित हैश फ़ंक्शन एच के साथ फिर से बनाया गया है<sub>j</sub>.
'''function''' Insert(''x'') '''is'''
    ''count'' = ''count'' + 1;
      '''if''' (''count'' > ''M'')
          FullRehash(''x'');
      '''end if'''
    '''else'''
        ''j'' = h(''x'');
        '''if''' (Position h<sub>''j''</sub>(x) of subtable ''T<sub>j</sub>'' contains ''x'')
            '''if''' (''x'' is marked deleted)
                remove the delete marker;
            '''end if'''
        '''end if'''
          '''else'''
            ''b<sub>j</sub>'' = ''b<sub>j</sub>'' + 1;
            '''if''' (''b<sub>j</sub>'' <= ''m<sub>j</sub>'')
                '''if''' position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'' is empty
                    store ''x'' in position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'';
                '''end if'''
                '''else'''
                      Put all unmarked elements of ''T<sub>j</sub>'' in list ''L<sub>j</sub>'';
                    Append ''x'' to list ''L<sub>j</sub>'';
                      ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';
                    '''repeat'''
                        ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
                    '''until''' ''h<sub>j</sub>'' is injective on the elements of ''L<sub>j</sub>'';
                    '''for''' all ''y'' on list ''L<sub>j</sub>''
                    store ''y'' in position h<sub>''j''</sub>(''y'') of ''T<sub>j</sub>'';
                '''end for'''
            '''end else'''
              '''end if else'''
                ''m<sub>j</sub>'' = 2 * max{1, ''m<sub>j</sub>''};
                ''s<sub>j</sub>'' = 2 * ''m<sub>j</sub>'' * (''m<sub>j</sub>'' - 1);
                '''if''' the sum total of all s<sub>j</sub> ≤ 32 * ''M''<sup>2</sup> / ''s''(''M'') + 4 * ''M''
                    Allocate ''s<sub>j</sub>'' cells for ''T<sub>j</sub>'';
                      Put all unmarked elements of ''T<sub>j</sub>'' in list ''L<sub>j</sub>'';
                    Append ''x'' to list ''L<sub>j</sub>'';
                    ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';
                    '''repeat'''
                        ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
                    '''until''' ''h<sub>j</sub>'' is injective on the elements of ''L<sub>j</sub>'';
                    '''for''' all ''y'' on list ''L<sub>j</sub>''
                    store ''y'' in position h<sub>''j''</sub>(''y'') of ''T<sub>j</sub>'';
                  '''end for'''
                '''end if'''


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


=== हटाएं ===
=== डिलीट ===


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


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


=== पूर्ण पुनर्निर्माण ===
    ''j'' = h(''x'');
    '''if''' position h<sub>j</sub>(''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 है<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>
<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"/>


फ़ंक्शन FullRehash(''x'') है
अंत में, प्रत्येक सबसेट्स T<sub>j</sub> के लिए हैश फ़ंक्शन H<sub>j</sub> को ''H<sub>sj</sub>'' से बार-बार यादृच्छिक रूप से चयन किया जाता है जब तक ''h<sub>j</sub>'' ,''T<sub>j</sub>'' के एलिमेंट्स पर प्रवेश न हो जाए। आकार n के साथ S की टेबल के फुल रिबिल्ड के लिए अपेक्षित समय O(n) है।<ref name="dietzfelbinger" />
     ''T'' के सभी अचिह्नित तत्वों को ''L'' सूची में रखें;
    '''function''' FullRehash(''x'') '''is'''
    यदि (''x'' ''U'' में है)
     Put all unmarked elements of ''T'' in list ''L'';
        ''x'' को ''L'' में जोड़ें;
        '''if''' (''x'' is in ''U'')  
     अगर अंत
    append ''x'' to ''L'';
    ''गिनती'' = सूची की लंबाई ''एल'';
     '''end if'''
     ''एम'' = (1 + ''सी'') * अधिकतम{''गिनती'', 4};
      ''count'' = length of list ''L'';
    दोहराना
     ''M'' = (1 + ''c'') * max{''count'', 4};
         h = ''H'' में यादृच्छिक रूप से चुना गया फ़ंक्शन<sub>s(M)</sub>;
        '''repeat'''
        'सभी के लिए' j < s(M)
         h = randomly chosen function in ''H<sub>s(M)</sub>'';
             एक सूची बनाएं एल<sub>j</sub>h(x) = j के लिए;
              '''for''' all ''j'' < ''s''(''M'')  
            बी<sub>j</sub>= L की लंबाई<sub>j</sub>;
             form a list ''L<sub>j</sub>'' for h(''x'') = ''j'';
            एम<sub>j</sub>= 2 * बी<sub>j</sub>;
              ''b<sub>j</sub>'' = length of ''L<sub>j</sub>'';  
            एस<sub>j</sub>= 2 * मी<sub>j</sub>* (एम<sub>j</sub>- 1);
            ''m<sub>j</sub>'' = 2 * ''b<sub>j</sub>'';  
        'के लिए अंत'
        ''s<sub>j</sub>'' = 2 * ''m<sub>j</sub>'' * (''m<sub>j</sub>'' - 1);
     'जब तक' सभी का योग न हो जाए<sub>j</sub> ≤ 32 * एम<sup>2</sup>/s(M) + 4 * M
      '''end for'''
    'सभी के लिए' j < s(M)
     '''until''' the sum total of all s<sub>j</sub> ≤ 32 * ''M''<sup>2</sup> / ''s''(''M'') + 4 * ''M''
         स्थान आवंटित करें<sub>j</sub>सबटेबल टी के लिए<sub>j</sub>;
        '''for''' all ''j'' < ''s''(''M'')  
        'दोहराना'
         Allocate space ''s<sub>j</sub>'' for subtable ''T<sub>j</sub>'';
            एच<sub>j</sub>= एच में यादृच्छिक रूप से चुना गया फ़ंक्शन<sub>sj</sub>;
              '''repeat'''  
        'जब तक' एच<sub>j</sub>सूची एल के तत्वों पर विशेषण है<sub>j</sub>;
          ''h<sub>j</sub>'' = randomly chosen function in ''H<sub>sj</sub>'';
     'के लिए अंत'
    '''until''' ''h<sub>j</sub>'' is injective on the elements of list ''L<sub>j</sub>'';
     सूची एल पर सभी एक्स के लिए 'के लिए'<sub>j</sub>x को स्थिति h में संग्रहित करें<sub>''j''</sub>(x) टी का<sub>j</sub>;
     '''end for'''
    'के लिए अंत'
     '''for''' all ''x'' on list ''L<sub>j</sub>''
  'अंत'
store ''x'' in position h<sub>''j''</sub>(''x'') of ''T<sub>j</sub>'';
 
'''end for'''
 
  '''end'''


==यह भी देखें==
==यह भी देखें==
* उत्तम हैशिंग
* परफेक्ट हैशिंग


==संदर्भ==
==संदर्भ==
{{reflist}}
{{reflist}}


{{DEFAULTSORT:Dynamic Perfect Hashing}}[[Category: हैशिंग]] [[Category: एल्गोरिदम खोजें]]
{{DEFAULTSORT:Dynamic Perfect Hashing}}
 
 


[[Category: Machine Translated Page]]
[[Category:All articles with dead external links]]
[[Category:Created On 10/07/2023]]
[[Category:Articles with dead external links from September 2017]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Dynamic Perfect Hashing]]
[[Category:Articles with permanently dead external links]]
[[Category:Created On 10/07/2023|Dynamic Perfect Hashing]]
[[Category:Lua-based templates|Dynamic Perfect Hashing]]
[[Category:Machine Translated Page|Dynamic Perfect Hashing]]
[[Category:Pages with script errors|Dynamic Perfect Hashing]]
[[Category:Templates Vigyan Ready|Dynamic Perfect Hashing]]
[[Category:Templates that add a tracking category|Dynamic Perfect Hashing]]
[[Category:Templates that generate short descriptions|Dynamic Perfect Hashing]]
[[Category:Templates using TemplateData|Dynamic Perfect Hashing]]
[[Category:Webarchive template wayback links]]
[[Category:एल्गोरिदम खोजें|Dynamic Perfect Hashing]]
[[Category:हैशिंग|Dynamic Perfect Hashing]]

Latest revision as of 10:10, 28 July 2023

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

विवरण

स्थैतिक केस

एफकेएस योजना

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

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

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

द्विघात आकार स्पेस यह सुनिश्चित करता है कि कलिसिएंस के साथ अव्यवस्थित रूप से टेबल बनाना दुर्लभ है और k, के आकार से स्वतंत्र है, जो रैखिक परिशोधन निर्माण समय प्रदान करता है। यद्यपि प्रत्येक दूसरे स्तर की टेबल में द्विघात स्थान की आवश्यकता होती है, यदि प्रथम स्तर की हैश टेबल में उत्पन्न की गई कीस समान रूप से वितरित की जाती हैं, तो समग्र रूप से स्ट्रक्चर अपेक्षित स्थान लेती है स्थान, चूंकि बकेट का आकार छोटा है और इसकी संभावना अधिक है।[1]

प्रथम-स्तरीय हैश फ़ंक्शन को विशेष रूप से चयन किया जाता है, जिससे x अद्वितीय की मानों के विशिष्ट सेट के लिए, सभी दूसरे-स्तरीय हैश टेबल द्वारा उपयोग की जाने वाली कुल स्थान T अपेक्षित हो स्थान, और अधिक विशेष रूप से फ्रेडमैन, कोमलोस और ज़ेमेरेडी ने दिखाया कि हैश फ़ंक्शंस के यूनिवर्सल हैशिंग फैमिली को देखते हुए, उनमें से कम से कम अर्ध फ़ंक्शंस में वह गुण होता है।[2]

डायनामिक केस

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

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

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

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

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

लोकेट

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 या सबटेबल Tj पर उपस्थित है, और विस्थापित किये गए के रूप में चिह्नित नहीं किया गया है, तो कहा जाता है कि कलिसिएंस होता है और jth बकेट की दूसरी-स्तरीय टेबल Tj को भिन्न यादृच्छिक रूप से चयनित हैश फ़ंक्शन hj के साथ फिर से बनाया गया है।

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 का आकार sj है, इसे तब तक बार-बार यादृच्छिक रूप से चयन किया जाता है:

अंत में, प्रत्येक सबसेट्स Tj के लिए हैश फ़ंक्शन Hj को Hsj से बार-बार यादृच्छिक रूप से चयन किया जाता है जब तक hj ,Tj के एलिमेंट्स पर प्रवेश न हो जाए। आकार n के साथ S की टेबल के फुल रिबिल्ड के लिए अपेक्षित समय O(n) है।[2]

    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

यह भी देखें

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

संदर्भ

  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#
  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]