परफेक्ट हैश फ़ंक्शन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(8 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Hash function without any collisions}}
{{Short description|Hash function without any collisions}}
[[File:Hash table 4 1 1 0 0 0 0 LL.svg|thumb|240px|right|दिखाए गए चार नामों के लिए एक आदर्श हैश फलन ]]
[[File:Hash table 4 1 1 0 0 0 0 LL.svg|thumb|240px|right|दिखाए गए चार नामों के लिए एक आदर्श हैश फ़ंक्शन ]]
[[File:Hash table 4 1 0 0 0 0 0 LL.svg|thumb|240px|right|दिखाए गए चार नामों के लिए एक न्यूनतम उत्तम हैश फलन ]][[कंप्यूटर विज्ञान]] में, एक आदर्श हैश फलन {{mvar|h}} एक समुच्चय के लिए {{mvar|S}} एक [[हैश फंकशन]] है जो अलग-अलग तत्वों को मानचित्र करता है {{mvar|S}} के एक समुच्चय के लिए {{mvar|m}} पूर्णांक, बिना किसी हैश टकराव के। गणितीय शब्दों में, यह एक [[इंजेक्शन समारोह|इंजेक्शन फलन]]  है।
[[File:Hash table 4 1 0 0 0 0 0 LL.svg|thumb|240px|right|दिखाए गए चार नामों के लिए एक न्यूनतम परफेक्ट हैश फ़ंक्शन ]]


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


परफेक्ट हैश फ़ंक्शंस के नुकसान ये हैं {{mvar|S}} को सही हैश फलन के निर्माण के लिए जाना जाना चाहिए। यदि गैर-गतिशील पूर्ण हैश फ़ंक्शंस को फिर से बनाने की आवश्यकता है {{mvar|S}} परिवर्तन। बार-बार बदलने के लिए {{mvar|S}} [[ गतिशील उत्तम हैशिंग |गतिशील उत्तम हैशिंग]] का उपयोग अतिरिक्त स्थान की कीमत पर किया जा सकता है।<ref name="DynamicPerfectHashing" />सही हैश फलन को संग्रहीत करने के लिए स्थान की आवश्यकता है {{math|''O''(''n'')}}.
कंप्यूटर विज्ञान में, सेट {{mvar|S}} के लिए एक '''परफेक्ट हैश फ़ंक्शन''' {{mvar|h}} एक हैश फ़ंक्शन है जो {{mvar|S}} में अलग-अलग तत्वों को {{mvar|m}} पूर्णांकों के सेट पर बिना किसी संघट्टन के मैप करता है। गणितीय शब्दों में, यह एक इंजेक्शन फ़ंक्शन है।


सही हैश फ़ंक्शंस के लिए महत्वपूर्ण प्रदर्शन पैरामीटर मूल्यांकन समय हैं, जो स्थिर होना चाहिए, निर्माण समय और प्रतिनिधित्व आकार।
निरंतर सबसे व्यर्थ स्थिति वाले एक्सेस समय के साथ लुकअप टेबल को प्रयुक्त करने के लिए परफेक्ट हैश फ़ंक्शंस का उपयोग किया जा सकता है। किसी भी हैश फ़ंक्शन की तरह, एक आदर्श हैश फ़ंक्शन का उपयोग हैश तालिकाओं को प्रयुक्त करने के लिए किया जा सकता है, इस लाभ के साथ कि कोई संघट्टन समाधान प्रयुक्त नहीं करना पड़ता है। इसके अतिरिक्त, यदि कुंजियाँ डेटा में नहीं हैं और यदि यह ज्ञात है कि क्वेरी की गई कुंजियाँ मान्य होंगी, तो कुंजियों को लुकअप टेबल में संग्रहीत करने की आवश्यकता नहीं है, जिससे स्थान की बचत होती है।
 
परफेक्ट हैश फ़ंक्शन का हानि यह है कि परफेक्ट हैश फ़ंक्शन के निर्माण के लिए {{mvar|S}} को जानना आवश्यक है। यदि {{mvar|S}} बदलता है तो गैर-गतिशील पूर्ण हैश फ़ंक्शंस को फिर से बनाने की आवश्यकता होती है। बार-बार बदलते एस डायनेमिक परफेक्ट हैश फ़ंक्शन के लिए अतिरिक्त स्थान की मूल्य पर उपयोग किया जा सकता है।<ref name="DynamicPerfectHashing">{{citation
| last1 = Dietzfelbinger | first1 = Martin
| last2 = Karlin | first2 = Anna | author2-link = Anna Karlin
| last3 = Mehlhorn | first3 = Kurt | author3-link = Kurt Mehlhorn
| last4 = Meyer auf der Heide | first4 = Friedhelm
| last5 = Rohnert | first5 = Hans
| last6 = Tarjan | first6 = Robert E. | author6-link = Robert Tarjan
| doi = 10.1137/S0097539791194094
| issue = 4
| journal = [[SIAM Journal on Computing]]
| mr = 1283572
| pages = 738–761
| title = Dynamic perfect hashing: upper and lower bounds
| volume = 23
| year = 1994}}.</ref> सही हैश फ़ंक्शन को संग्रहीत करने के लिए स्थान की आवश्यकता {{math|''O''(''n'')}} में है।
 
सही हैश फ़ंक्शंस के लिए महत्वपूर्ण प्रदर्शन पैरामीटर मूल्यांकन समय हैं जो निर्माण समय और प्रतिनिधित्व आकार के अनुरूप होना चाहिए।


==आवेदन==
==आवेदन==
सीमित सीमा में मानों के साथ एक आदर्श हैश फलन का उपयोग कुशल लुकअप संचालन के लिए कुंजी लगाकर किया जा सकता है {{mvar|S}} (या अन्य संबद्ध मान) फलन के आउटपुट द्वारा अनुक्रमित लुकअप तालिका में। इसके पश्चात् कोई यह जांच सकता है कि कोई कुंजी मौजूद है या नहीं {{mvar|S}}, या तालिका के सेल में उस कुंजी की तलाश करके उससे जुड़े मान को देखें। सबसे खराब स्थिति की जटिलता में ऐसे प्रत्येक लुकअप में लगातार समय लगता है।<ref name="inventor"/>सही हैशिंग के साथ, संबंधित डेटा को तालिका तक एकल पहुंच के साथ पढ़ा या लिखा जा सकता है।<ref>{{citation
फ़ंक्शन के आउटपुट द्वारा अनुक्रमित लुकअप टेबल में {{mvar|S}} (या अन्य संबंधित मान) से कुंजी रखकर, सीमित सीमा में मानों के साथ एक आदर्श हैश फ़ंक्शन का उपयोग कुशल लुकअप संचालन के लिए किया जा सकता है। इसके बाद कोई यह परीक्षण कर सकता है कि कोई कुंजी {{mvar|S}} में उपस्थित है या नहीं, या टेबल के सेल में उस कुंजी को देखकर उससे जुड़े मान को देख सकता है। सबसे व्यर्थ स्थिति में ऐसे प्रत्येक लुकअप में निरंतर समय लगता है।<ref name="inventor">{{citation
| last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
| last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi
| doi = 10.1145/828.1884
| issue = 3
| journal = [[Journal of the ACM]]
| mr = 0819156
| page = 538
| title = Storing a Sparse Table with {{math|''O''(1)}} Worst Case Access Time
| volume = 31
| year = 1984| s2cid = 5399743 }}</ref> सही हैशिंग के साथ, संबंधित डेटा को टेबल तक एकल पहुंच के साथ पढ़ा या लिखा जा सकता है।<ref>{{citation
  | last1 = Lu | first1 = Yi | author1-link = Yi Lu (computer scientist)
  | last1 = Lu | first1 = Yi | author1-link = Yi Lu (computer scientist)
  | last2 = Prabhakar | first2 = Balaji | author2-link = Balaji Prabhakar
  | last2 = Prabhakar | first2 = Balaji | author2-link = Balaji Prabhakar
Line 19: Line 47:
  | title = Perfect Hashing for Network Applications
  | title = Perfect Hashing for Network Applications
  | year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref>
  | year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref>
==परफेक्ट हैश फ़ंक्शंस का प्रदर्शन==
सही हैशिंग के लिए महत्वपूर्ण प्रदर्शन पैरामीटर प्रतिनिधित्व आकार, मूल्यांकन समय, निर्माण समय और इसके अतिरिक्त सीमा आवश्यकता<math>\frac{m}{n}</math> हैं।<ref name="CHD">{{citation
| last1 = Belazzougui | first1 = Djamal
| last2 = Botelho | first2 = Fabiano C.
| last3 = Dietzfelbinger | first3 = Martin
| contribution = Hash, displace, and compress
| contribution-url = http://cmph.sourceforge.net/papers/esa09.pdf
| doi = 10.1007/978-3-642-04128-0_61
| location = Berlin
| mr = 2557794
| pages = 682–693
| publisher = Springer
| series = [[Lecture Notes in Computer Science]]
| title = Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings
| volume = 5757
| year = 2009| citeseerx = 10.1.1.568.130
| url = http://cmph.sourceforge.net/papers/esa09.pdf
}}.</ref> मूल्यांकन का समय {{math|''O''(''1'')}} जितना तेज़ हो सकता है, जो इष्टतम है<ref name="inventor"/><ref name="CHD"/> निर्माण का समय कम से कम {{math|''O''(''n'')}} होना चाहिए, क्योंकि {{mvar|S}} में प्रत्येक तत्व पर विचार करने की आवश्यकता है, और {{mvar|S}} में {{mvar|n}} तत्व सम्मिलित हैं। इस निचली सीमा को वास्तव में प्राप्त किया जा सकता है।<ref name="CHD"/>




==उत्तम हैश फ़ंक्शंस का प्रदर्शन==
प्रतिनिधित्व आकार की निचली सीमा {{mvar|m}} और {{mvar|n}} पर निर्भर करती है। मान लीजिए {{math|''m'' {{=}} (1+&epsilon;) ''n''}} और {{mvar|h}} एक आदर्श हैश फ़ंक्शन है। निचली सीमा के लिए एक अच्छा सन्निकटन <math>\log e - \varepsilon \log \frac{1+\varepsilon}{\varepsilon}</math> बिट्स प्रति तत्व है। न्यूनतम पूर्ण हैशिंग के लिए, {{math|&epsilon; {{=}} 0}}, निचली सीमा {{math|log e ≈ 1.44}} बिट प्रति तत्व है।<ref name="CHD"/>
सही हैशिंग के लिए महत्वपूर्ण प्रदर्शन पैरामीटर प्रतिनिधित्व आकार, मूल्यांकन समय, निर्माण समय और इसके अतिरिक्त सीमा की आवश्यकता हैं <math>\frac{m}{n}</math>.<ref name="CHD"/>मूल्यांकन का समय उतना ही तेज़ हो सकता है {{math|''O''(''1'')}}, जो इष्टतम है.<ref name="inventor"/><ref name="CHD"/>निर्माण का समय कम से कम होना चाहिए {{math|''O''(''n'')}}, क्योंकि प्रत्येक तत्व में {{mvar|S}} पर विचार करने की आवश्यकता है, और {{mvar|S}} रोकना {{mvar|n}}तत्व. इस निचली सीमा को व्यवहार में हासिल किया जा सकता है।<ref name="CHD"/>
 
प्रतिनिधित्व आकार के लिए निचली सीमा निर्भर करती है {{mvar|m}} और {{mvar|n}}. होने देना {{math|''m'' {{=}} (1+&epsilon;) ''n''}} और {{mvar|h}} एक आदर्श हैश फलन । निचली सीमा के लिए एक अच्छा सन्निकटन है <math>\log e - \varepsilon \log \frac{1+\varepsilon}{\varepsilon}</math> प्रति तत्व बिट्स. न्यूनतम उत्तम हैशिंग के लिए, {{math|&epsilon; {{=}} 0}}, निचली सीमा है {{math|log e ≈ 1.44}} प्रति तत्व बिट्स।<ref name="CHD"/>
 
 
==निर्माण==
==निर्माण==
एक विशिष्ट समुच्चय के लिए एक आदर्श हैश फलन {{mvar|S}} जिसका मूल्यांकन निरंतर समय में किया जा सकता है, और एक छोटी सी सीमा में मूल्यों के साथ, [[यादृच्छिक एल्गोरिदम]] द्वारा अनेक ऑपरेशनों में पाया जा सकता है जो एस के आकार के लिए आनुपातिक है।
एक विशिष्ट सेट {{mvar|S}} के लिए एक आदर्श हैश फ़ंक्शन जिसका मूल्यांकन निरंतर समय में किया जा सकता है, और एक छोटी सी सीमा में मूल्यों के साथ, यादृच्छिक एल्गोरिदम द्वारा कई ऑपरेशनों में पाया जा सकता है जो {{mvar|S}} के आकार के लिए आनुपातिक है। का मूल निर्माण फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) {{mvar|n}} तत्वों के सेट {{mvar|S}} को {{math|''O''(''n'')}} सूचकांकों की एक श्रृंखला में मैप करने के लिए दो-स्तरीय योजना का उपयोग करते हैं, और फिर प्रत्येक सूचकांक को हैश मानों की एक श्रृंखला में मैप करते हैं। उनके निर्माण का पहला स्तर एक बड़े प्राइम {{mvar|p}} (ब्रह्मांड के आकार से बड़ा जहां से {{mvar|S}} खींचा गया है) और एक पैरामीटर {{mvar|k}} को चुनता है, और {{mvar|S}} के प्रत्येक तत्व {{mvar|x}} को सूचकांक में मैप करता है।
का मूल निर्माण {{harvtxt|Fredman|Komlós|Szemerédi|1984}} किसी समुच्चय को मानचित्र करने के लिए दो-स्तरीय योजना का उपयोग करता है {{mvar|S}} का {{mvar|n}} तत्वों की एक श्रृंखला के लिए {{math|''O''(''n'')}} सूचकांक, और फिर प्रत्येक सूचकांक को हैश मानों की श्रेणी में मानचित्र करें। इनके निर्माण का प्रथम स्तर एक बड़े प्राइम को चुनता है {{mvar|p}} ([[ब्रह्मांड (गणित)]] के आकार से भी बड़ा {{mvar|S}} खींचा गया है), और एक पैरामीटर {{mvar|k}}, और प्रत्येक तत्व को मानचित्र करता है {{mvar|x}} का {{mvar|S}} सूचकांक के लिए
:<math>g(x)=(kx\bmod p)\bmod n.</math>
:<math>g(x)=(kx\bmod p)\bmod n.</math>
अगर {{mvar|k}} को यादृच्छिक रूप से चुना जाता है, इस चरण में टकराव होने की संभावना है, लेकिन तत्वों की संख्या {{mvar|n<sub>i</sub>}} जो एक साथ एक ही सूचकांक पर मानचित्र किए जाते हैं {{mvar|i}} छोटा होने की संभावना है.
यदि {{mvar|k}} को यादृच्छिक रूप से चुना जाता है, तो इस चरण में संघट्टन होने की संभावना है, किन्तु एक ही सूचकांक {{mvar|i}} पर एक साथ मैप किए गए तत्वों {{mvar|n<sub>i</sub>}} की संख्या छोटी होने की संभावना है। उनके निर्माण का दूसरा स्तर प्रत्येक सूचकांक {{mvar|i}} के लिए {{math|''O''(''n<sub>i</sub>''<sup>2</sup>)}} पूर्णांकों की असंयुक्त श्रेणियाँ निर्दिष्ट करता है। यह {{mvar|S}} के प्रत्येक सदस्य {{mvar|x}} को {{math|''g''(''x'')}} से जुड़ी सीमा में मैप करने के लिए, प्रत्येक सूचकांक {{mvar|i}} के लिए रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे सेट का उपयोग करता है।<ref name="inventor" />
उनके निर्माण का दूसरा स्तर असंयुक्त श्रेणियाँ निर्दिष्ट करता है {{math|''O''(''n<sub>i</sub>''<sup>2</sup>)}}प्रत्येक सूचकांक के लिए पूर्णांक {{mvar|i}}. यह रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे समुच्चय का उपयोग करता है, प्रत्येक सूचकांक के लिए एक {{mvar|i}}, प्रत्येक सदस्य को मानचित्र करने के लिए {{mvar|x}} का {{mvar|S}} से जुड़ी सीमा में {{math|''g''(''x'')}}.<ref name="inventor">{{citation
 
| last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
जैसा कि फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) दिखाते हैं, पैरामीटर {{mvar|k}} का एक विकल्प उपस्थित है जैसे कि {{math|''g''(''x'')}} के n विभिन्न मानों के लिए श्रेणियों की लंबाई का योग{{math|''O''(''n'')}} है। इसके अतिरिक्त, {{math|''g''(''x'')}} के प्रत्येक मान के लिए, एक रैखिक मॉड्यूलर फ़ंक्शन उपस्थित होता है जो {{mvar|S}} के संबंधित उपसमुच्चय को उस मान से जुड़ी सीमा में मैप करता है। दोनों k, और {{math|''g''(''x'')}} के प्रत्येक मान के लिए दूसरे स्तर के फ़ंक्शन, बहुपद समय में मानों को यादृच्छिक रूप से चुनकर तब तक पाए जा सकते हैं जब तक कि कोई कार्य न मिल जाए।<ref name="inventor" />
| last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
| last3 = Szemerédi | first3 = Endre | author3-link = Endre Szemerédi
| doi = 10.1145/828.1884
| issue = 3
| journal = [[Journal of the ACM]]
| mr = 0819156
| page = 538
| title = Storing a Sparse Table with {{math|''O''(1)}} Worst Case Access Time
| volume = 31
| year = 1984| s2cid = 5399743 }}</ref>
जैसा {{harvtxt|Fredman|Komlós|Szemerédi|1984}}दिखाएँ, पैरामीटर का एक विकल्प मौजूद है {{mvar|k}} जैसे कि श्रेणियों की लंबाई का योग {{mvar|n}} के विभिन्न मान {{math|''g''(''x'')}} है {{math|''O''(''n'')}}. इसके अतिरिक्त, प्रत्येक मान के लिए {{math|''g''(''x'')}}, एक रैखिक मॉड्यूलर फलन मौजूद है जो संबंधित उपसमुच्चय को मानचित्र करता है {{mvar|S}} उस मान से संबद्ध सीमा में। दोनों {{mvar|k}}, और प्रत्येक मान के लिए दूसरे स्तर के फलन {{math|''g''(''x'')}}, बहुपद समय में मानों को यादृच्छिक रूप से चुनकर तब तक पाया जा सकता है जब तक कि कोई कार्यशील मान न मिल जाए।<ref name="inventor"/>


हैश फलन को स्वयं संग्रहण स्थान की आवश्यकता होती है {{math|''O''(''n'')}} संचय करना {{mvar|k}}, {{mvar|p}}, और दूसरे स्तर के सभी रैखिक मॉड्यूलर फलन । किसी दी गई कुंजी के हैश मान की गणना करना {{mvar|x}} कंप्यूटिंग द्वारा निरंतर समय में निष्पादित किया जा सकता है {{math|''g''(''x'')}}, से जुड़े दूसरे स्तर के फलन को देख रहे हैं {{math|''g''(''x'')}}, और इस फलन को क्रियान्वित करना {{mvar|x}}.
हैश फ़ंक्शन को {{mvar|k}}, {{mvar|p}} और सभी दूसरे स्तर के रैखिक मॉड्यूलर फ़ंक्शंस को संग्रहीत करने के लिए संचयन स्थान {{math|''O''(''n'')}} की आवश्यकता होती है। किसी दिए गए कुंजी {{mvar|x}} के हैश मान की गणना निरंतर समय में {{math|''g''(''x'')}} की गणना करके, {{math|''g''(''x'')}} से जुड़े दूसरे स्तर के फ़ंक्शन को देखकर और इस फ़ंक्शन को {{mvar|x}} पर प्रयुक्त करके की जा सकती है। शीर्ष स्तर पर बड़ी संख्या में मानों के साथ इस दो-स्तरीय योजना का एक संशोधित संस्करण एक आदर्श हैश फ़ंक्शन के निर्माण के लिए उपयोग किया जा सकता है जो एस को लंबाई {{math|''n'' + ''o''(''n'')}} की एक छोटी श्रृंखला में मैप करता है।<ref name="inventor" />
शीर्ष स्तर पर बड़ी संख्या में मानों के साथ इस दो-स्तरीय योजना का एक संशोधित संस्करण का उपयोग एक आदर्श हैश फलन बनाने के लिए किया जा सकता है जो मानचित्र करता है {{mvar|S}} लंबाई की एक छोटी सीमा में {{math|''n'' + ''o''(''n'')}}.<ref name="inventor"/>


एक आदर्श हैश फलन के निर्माण के लिए एक और हालिया विधि का वर्णन किया गया है हैश, डिसप्लेस और कंप्रेस के रूप में। यहां प्रथम-स्तरीय हैश फलन है {{mvar|g}} का उपयोग तत्वों को किसी श्रेणी में मानचित्र करने के लिए भी किया जाता है {{mvar|r}} पूर्णांक. तत्व {{math|''x'' ∈ ''S''}} को बाल्टी में संग्रहित किया जाता है {{mvar|B<sub>g(x)</sub>}}.<ref name="CHD" />
परफेक्ट हैश फ़ंक्शन के निर्माण के लिए एक और आधुनिक विधि को बेलाज़ौगुई, बोटेल्हो और डिट्ज़फेलबिंगर (2009) ने "हैश, डिस्प्लेस और कंप्रेस" के रूप में वर्णित किया है। यहां प्रथम-स्तरीय हैश फ़ंक्शन {{mvar|g}} का उपयोग तत्वों को {{mvar|r}} पूर्णांकों की श्रेणी में मैप करने के लिए भी किया जाता है। एक तत्व {{math|''x'' ∈ ''S''}} को बकेट {{mvar|B<sub>g(x)</sub>}} में संग्रहीत किया जाता है।<ref name="CHD" />


फिर, आकार के घटते क्रम में, प्रत्येक बाल्टी के तत्वों को स्वतंत्र पूर्ण यादृच्छिक हैश फलन के अनुक्रम के हैश फलन द्वारा हैश किया जाता है {{math|(&Phi;<sub>1</sub>, &Phi;<sub>2</sub>, &Phi;<sub>3</sub>, ...)}}, प्रारंभ स्थल {{math|&Phi;<sub>1</sub>}}. यदि हैश फलन बकेट के लिए कोई टकराव उत्पन्न नहीं करता है, और परिणामी मान अभी तक अन्य बकेट के अन्य तत्वों द्वारा कब्जा नहीं किया गया है, तब उस बकेट के लिए फलन चुना जाता है। यदि नहीं, तब अनुक्रम में अगले हैश फलन का परीक्षण किया जाता है।<ref name="CHD" />
फिर, आकार के घटते क्रम में, प्रत्येक बकेट के तत्वों को {{math|&Phi;<sub>1</sub>}} से प्रारंभ करके स्वतंत्र पूर्ण यादृच्छिक हैश फ़ंक्शन {{math|(&Phi;<sub>1</sub>, &Phi;<sub>2</sub>, &Phi;<sub>3</sub>, ...)}} के अनुक्रम के हैश फ़ंक्शन द्वारा हैश किया जाता है। यदि हैश फ़ंक्शन बकेट के लिए कोई संघट्टन उत्पन्न नहीं करता है, और परिणामी मान अभी तक अन्य बकेट के अन्य तत्वों द्वारा अधिकृत नहीं किया गया है, तो उस बकेट के लिए फ़ंक्शन चुना जाता है। यदि नहीं, तो अनुक्रम में अगले हैश फ़ंक्शन का परीक्षण किया जाता है।<ref name="CHD" />


सही हैश फलन का मूल्यांकन करने के लिए {{math|''h''(''x'')}} किसी को केवल बकेट इंडेक्स की मैपिंग σ को सहेजना होगा {{math|''g''(''x'')}} अनुक्रम में सही हैश फलन पर, जिसके परिणामस्वरूप {{math|h(x) {{=}} &Phi;<sub>σ(g(x))</sub>}}.<ref name="CHD" />
सही हैश फ़ंक्शन {{math|''h''(''x'')}} का मूल्यांकन करने के लिए किसी को केवल अनुक्रम में सही हैश फ़ंक्शन पर बकेट इंडेक्स {{math|''g''(''x'')}} की मैपिंग σ को सहेजना होगा, जिसके परिणामस्वरूप {{math|h(x) {{=}} &Phi;<sub>σ(g(x))</sub>}} होगा।<ref name="CHD" />


अंत में, प्रतिनिधित्व आकार को कम करने के लिए, ({{math|σ(i))<sub>0 ≤ i < r</sub>}} को एक ऐसे रूप में संपीड़ित किया जाता है जो अभी भी मूल्यांकन की अनुमति देता है {{math|''O''(''1'')}}.<ref name="CHD" />
अंत में, प्रतिनिधित्व आकार को कम करने के लिए,{{math|σ(i))<sub>0 ≤ i < r</sub>}} को एक ऐसे रूप में संपीड़ित किया जाता है जो अभी भी {{math|''O''(''1'')}} में मूल्यांकन की अनुमति देता है।<ref name="CHD" />


इस दृष्टिकोण के लिए रैखिक समय की आवश्यकता है {{mvar|n}} निर्माण के लिए, और निरंतर मूल्यांकन समय। प्रतिनिधित्व आकार में है {{math|''O''(''n'')}}, और प्राप्त सीमा पर निर्भर करता है। उदाहरण के लिए, साथ {{math|''m'' {{=}} 1.23''n''}} ने 10 मिलियन प्रविष्टियों के दिए गए उदाहरण समुच्चय के लिए 3.03 बिट्स/कुंजी और 1.40 बिट्स/कुंजी के मध्य एक प्रतिनिधित्व आकार हासिल किया, कम मूल्यों के लिए उच्च गणना समय की आवश्यकता होती है। इस परिदृश्य में निचली सीमा 0.88 बिट/कुंजी है।<ref name="CHD" />
इस दृष्टिकोण को निर्माण के लिए {{mvar|n}} में रैखिक समय और निरंतर मूल्यांकन समय की आवश्यकता होती है। प्रतिनिधित्व का आकार {{math|''O''(''n'')}} में है, और प्राप्त सीमा पर निर्भर करता है। उदाहरण के लिए, {{math|''m'' {{=}} 1.23''n''}} के साथ बेलाज़ौगुई, बोटेल्हो और डाइट्ज़फेलबिंगर (2009) ने 10 मिलियन प्रविष्टियों के अपने दिए गए उदाहरण सेट के लिए 3.03 बिट्स/कुंजी और 1.40 बिट्स/कुंजी के बीच एक प्रतिनिधित्व आकार प्राप्त किया, कम मूल्यों के लिए उच्च गणना समय की आवश्यकता होती है। इस परिदृश्य में निचली सीमा 0.88 बिट/कुंजी है।<ref name="CHD" />
===छद्मकोड===
===छद्मकोड===
एल्गोरिथम ''हैश, डिस्प्लेस, और कंप्रेस'' है
<syntaxhighlight>
(1) एस को बाल्टियों में विभाजित करें {{math|B<sub>i</sub> :{{=}} g<sup>−1</sup>({i})&cap;S,0 ≤ i < r}}
algorithm hash, displace, and compress is
(2) बाल्टियाँ बी क्रमबद्ध करें<sub>i</sub> आकार के अनुसार घटते क्रम में |बी<sub>i</sub>|
(1) Split S into buckets Bi := g−1({i})∩S,0 ≤ i < r
(3) सरणी T[0...m-1] को 0 से प्रारंभ करें
(2) Sort buckets Bi in falling order according to size |Bi|
(4) सभी के लिए I{{thin space}}∈[r], (2) से क्रम में करें
(3) Initialize array T[0...m-1] with 0's
(5) एल के लिए{{thin space}}←{{thin space}}1,2,...
(4) for all i ∈[r], in the order from (2), do
(6) K बनाते हुए दोहराएँ<sub>i</sub>{{thin space}}←{{thin space}}{{{math|&Phi;}}<sub>l</sub>(x)|x{{thin space}}∈{{thin space}}B<sub>i</sub>}
(5)     for l ← 1,2,...
(6) जब तक |के<sub>i</sub>|=|बी<sub>i</sub>| और के<sub>i</sub>∩{j|T[j]=1}={{thin space}}&खाली समुच्चय ;
(6)         repeat forming Ki ← {Φl(x)|x ∈ Bi}
(7) चलो σ(i):= सफल एल
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=1}= ∅
(8) सभी जे के लिए{{thin space}}∈{{thin space}}क<sub>i</sub> चलो टी[जे]:={{thin space}}1
(7)     let σ(i):= the successful l
(9) परिवर्तन (पृ<sub>i</sub>)<sub>0&le;i<r</sub> संपीड़ित रूप में, बनाए रखना {{math|''O''(''1'')}} पहुँच।
(8)     for all j ∈ Ki let T[j]:= 1
 
(9) Transform (σi)0≤i<r into compressed form, retaining O(1) access.
</syntaxhighlight>
==अंतरिक्ष निचली सीमा==
==अंतरिक्ष निचली सीमा==
का उपयोग {{math|''O''(''n'')}} कार्य को संग्रहीत करने के लिए जानकारी के शब्द लगभग-इष्टतम है: कोई भी पूर्ण हैश फलन जिसकी गणना निरंतर समय में की जा सकती है
फ्रेडमैन कोमलोस और ज़ेमेरेडी (1984) के फ़ंक्शन को संग्रहीत करने के लिए जानकारी के {{math|''O''(''n'')}} शब्दों का उपयोग लगभग इष्टतम है: किसी भी सही हैश फ़ंक्शन की गणना निरंतर समय में की जा सकती है जिसके लिए कम से कम कई बिट्स की आवश्यकता होती है जो आनुपातिक हो {{mvar|S}} का आकार का है <ref>{{citation
के आकार के समानुपाती कम से कम बिट्स की संख्या की आवश्यकता होती है {{mvar|S}}.<ref>{{citation
  | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
  | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
  | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
  | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
Line 84: Line 112:
  | volume = 5
  | volume = 5
  | year = 1984}}.</ref>
  | year = 1984}}.</ref>
न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है
न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है
:<math>\log_2e\approx1.44</math>
:<math>\log_2e\approx1.44</math>
बिट्स/कुंजी.<ref name="CHD" />
बिट्स/कुंजी.<ref name="CHD" />


सही हैश फ़ंक्शंस के लिए, सबसे पहले यह माना जाता है कि की सीमा {{mvar|h}} से घिरा है {{mvar|n}} जैसा {{math|''m'' {{=}} (1+&epsilon;) ''n''}}. द्वारा दिए गए सूत्र के साथ और एक ब्रह्मांड के लिए (गणित) <math>U\supseteq S</math> जिसका आकार {{math|{{!}}''U''{{!}} {{=}} ''u''}} अनंत की ओर जाता है, अंतरिक्ष निचली सीमा है
सही हैश फ़ंक्शंस के लिए, सबसे पहले यह माना जाता है कि की सीमा {{mvar|h}} से घिरा है {{mvar|n}} जैसा {{math|''m'' {{=}} (1+&epsilon;) ''n''}}. द्वारा दिए गए सूत्र के साथ और एक ब्रह्मांड के लिए (गणित) <math>U\supseteq S</math> जिसका आकार {{math|{{!}}''U''{{!}} {{=}} ''u''}} अनंत की ओर जाता है, निचली सीमा में स्थित है
:<math>\log_2e-\varepsilon \log\frac{1+\varepsilon}{\varepsilon}</math>
:<math>\log_2e-\varepsilon \log\frac{1+\varepsilon}{\varepsilon}</math>
बिट्स/कुंजी, माइनस {{math|log(''n'')}} कुल मिलाकर बिट्स।<ref name="CHD" />


बिट्स/कुंजी, कुल मिलाकर माइनस {{math|log(''n'')}} बिट्स है।<ref name="CHD" />
==एक्सटेंशन==
==एक्सटेंशन==


===मेमोरी पता पहचान===
===मेमोरी एड्रेस पहचान===
परफेक्ट हैशिंग का एक तुच्छ लेकिन व्यापक उदाहरण कंप्यूटर की (वर्चुअल) [[ आभासी मेमोरी |आभासी मेमोरी]] में निहित है। चूँकि वर्चुअल मेमोरी का प्रत्येक बाइट एक विशिष्ट, अद्वितीय, सीधे पता योग्य भंडारण स्थान है, मेमोरी में संग्रहीत (प्रारंभिक) [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] के मूल्य को संपूर्ण मेमोरी एड्रेस रेंज में उस ऑब्जेक्ट का एक वास्तविक सही हैश माना जा सकता है।<ref>{{cite book|publisher=[[Springer Science+Business Media]]|url=https://books.google.com/books?id=66jBbZYOt-EC&pg=PA254|page=254|author1=Witold Litwin|author2=Tadeusz Morzy|author3=Gottfried Vossen|date=19 August 1998|isbn= 9783540649243|title=Advances in Databases and Information Systems}}</ref>
परफेक्ट हैशिंग का एक तुच्छ किन्तु व्यापक उदाहरण कंप्यूटर की (वर्चुअल) [[ आभासी मेमोरी |वर्चुअल मेमोरी]] में निहित है। चूँकि वर्चुअल मेमोरी का प्रत्येक बाइट एक विशिष्ट, अद्वितीय, सीधे पता योग्य संचयन स्थान है, मेमोरी में संग्रहीत (प्रारंभिक) [[पॉइंटर (कंप्यूटर प्रोग्रामिंग)]] के मूल्य को संपूर्ण मेमोरी एड्रेस रेंज में उस ऑब्जेक्ट का एक वास्तविक सही हैश माना जा सकता है।<ref>{{cite book|publisher=[[Springer Science+Business Media]]|url=https://books.google.com/books?id=66jBbZYOt-EC&pg=PA254|page=254|author1=Witold Litwin|author2=Tadeusz Morzy|author3=Gottfried Vossen|date=19 August 1998|isbn= 9783540649243|title=Advances in Databases and Information Systems}}</ref>




===गतिशील उत्तम हैशिंग===
===गतिशील परफेक्ट हैशिंग===
एक आदर्श हैश फलन का उपयोग करना उन स्थितियों में सबसे अच्छा है जहां बार-बार पूछे जाने वाले बड़े समुच्चय होते हैं, {{mvar|S}}, जिसे शायद ही कभी अद्यतन किया जाता है। इसका कारण समुच्चय का कोई भी संशोधन है {{mvar|S}} संशोधित समुच्चय के लिए हैश फलन अब सही नहीं रह सकता है। ऐसे समाधान जो किसी भी समय समुच्चय को संशोधित करने पर हैश फलन को अपडेट करते हैं उन्हें डायनामिक परफेक्ट हैशिंग के रूप में जाना जाता है,<ref name="DynamicPerfectHashing">{{citation
एक सही हैश फ़ंक्शन का उपयोग करना उन स्थितियों में सबसे अच्छा है जहां बार-बार पूछे जाने वाले बड़े सेट, {{mvar|S}}, जो संभवतः ही कभी अपडेट किया जाता है। ऐसा इसलिए है क्योंकि सेट {{mvar|S}} के किसी भी संशोधन के कारण हैश फ़ंक्शन संशोधित सेट के लिए बिल्कुल सही नहीं रह सकता है। ऐसे समाधान जो किसी भी समय सेट को संशोधित करने पर हैश फ़ंक्शन को अपडेट करते हैं, उन्हें डायनेमिक परफेक्ट हैशिंग के रूप में जाना जाता है<ref name="DynamicPerfectHashing" /> किन्तु इन विधियों को प्रयुक्त करना अपेक्षाकृत समष्टि है।
| last1 = Dietzfelbinger | first1 = Martin
| last2 = Karlin | first2 = Anna | author2-link = Anna Karlin
| last3 = Mehlhorn | first3 = Kurt | author3-link = Kurt Mehlhorn
| last4 = Meyer auf der Heide | first4 = Friedhelm
| last5 = Rohnert | first5 = Hans
| last6 = Tarjan | first6 = Robert E. | author6-link = Robert Tarjan
| doi = 10.1137/S0097539791194094
| issue = 4
| journal = [[SIAM Journal on Computing]]
| mr = 1283572
| pages = 738–761
| title = Dynamic perfect hashing: upper and lower bounds
| volume = 23
| year = 1994}}.</ref> लेकिन इन तरीकों को क्रियान्वित करना अपेक्षाकृत जटिल है।


===न्यूनतम उत्तम हैश फलन ===
===न्यूनतम परफेक्ट हैश फ़ंक्शन ===
न्यूनतम परफेक्ट हैश फलन एक परफेक्ट हैश फलन है जो मानचित्र करता है {{mvar|n}}की चाबियाँ {{mvar|n}} लगातार पूर्णांक - आमतौर पर संख्याएँ {{math|0}} को {{math|''n'' &minus; 1}} या से {{math|1}} को {{mvar|n}}. इसे व्यक्त करने का एक अधिक औपचारिक तरीका है: चलो {{mvar|j}} और {{mvar|k}} किसी परिमित समुच्चय के तत्व हों {{mvar|S}}. तब {{mvar|h}} एक न्यूनतम पूर्ण हैश फलन है यदि और केवल यदि {{math|1=''h''(''j'') = ''h''(''k'')}} तात्पर्य {{math|1=''j'' = ''k''}} ([[ इंजेक्शन ]]) और एक पूर्णांक मौजूद है {{mvar|a}} ऐसा कि की सीमा {{mvar|h}} है {{math|1=''a''..''a'' + {{!}}''S''{{!}} &minus; 1}}. यह सिद्ध हो चुका है कि एक सामान्य प्रयोजन न्यूनतम उत्तम हैश योजना के लिए कम से कम आवश्यकता होती है {{math|lg ''e'' ≈ 1.44}} बिट्स/कुंजी।<ref name="CHD">{{citation
न्यूनतम पूर्ण हैश फ़ंक्शन एक पूर्ण हैश फ़ंक्शन है जो n कुंजियों को n निरन्तर पूर्णांकों में मैप करता है - सामान्यतः 0 से n - 1 या 1 से n तक की संख्याएँ है इसे व्यक्त करने का एक अधिक औपचारिक विधि यह है: मान लीजिए कि j और k कुछ परिमित समुच्चय S के तत्व हैं। तब h एक न्यूनतम पूर्ण हैश फ़ंक्शन है यदि और केवल यदि {{math|1=''h''(''j'') = ''h''(''k'')}} का तात्पर्य {{math|1=''j'' = ''k''}}(इंजेक्टिविटी) है और एक पूर्णांक a इस प्रकार उपस्थित है कि h का परिसर {{math|1=''a''..''a'' + {{!}}''S''{{!}} &minus; 1}} है यह सिद्ध हो चुका है कि एक सामान्य प्रयोजन न्यूनतम परफेक्ट हैश योजना के लिए कम से कम {{math|lg ''e'' ≈ 1.44}} बिट्स/कुंजी की आवश्यकता होती है।<ref name="CHD" /> यद्यपि यह स्थान सैद्धांतिक कार्यों द्वारा प्राप्त किया गया है, व्यवहार में, सबसे प्रसिद्ध न्यूनतम परफेक्ट हैशिंग योजनाओं के लिए पर्याप्त समय दिए जाने पर लगभग 1.56 बिट्स/कुंजी की आवश्यकता होती है।<ref name="RecSplit">{{citation
| last1 = Belazzougui | first1 = Djamal
| last2 = Botelho | first2 = Fabiano C.
| last3 = Dietzfelbinger | first3 = Martin
| contribution = Hash, displace, and compress
| contribution-url = http://cmph.sourceforge.net/papers/esa09.pdf
| doi = 10.1007/978-3-642-04128-0_61
| location = Berlin
| mr = 2557794
| pages = 682–693
| publisher = Springer
| series = [[Lecture Notes in Computer Science]]
| title = Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings
| volume = 5757
| year = 2009| citeseerx = 10.1.1.568.130
| url = http://cmph.sourceforge.net/papers/esa09.pdf
}}.</ref> यद्यपि यह स्थान सैद्धांतिक कार्यों द्वारा हासिल किया गया है, व्यवहार में, सबसे प्रसिद्ध न्यूनतम सही हैशिंग योजनाओं को पर्याप्त समय दिए जाने पर लगभग 1.56 बिट्स/कुंजी की आवश्यकता होती है।<ref name="RecSplit">{{citation
  | last1 = Esposito | first1 = Emmanuel
  | last1 = Esposito | first1 = Emmanuel
  | last2 = Mueller Graf | first2 = Thomas
  | last2 = Mueller Graf | first2 = Thomas
Line 149: Line 147:


===k-परफेक्ट हैशिंग===
===k-परफेक्ट हैशिंग===
एक हैश फलन है {{mvar|k}}-यदि अधिक से अधिक हो तब उत्तम {{mvar|k}}तत्वों से {{mvar|S}} को श्रेणी में समान मान पर मानचित्र किया जाता है। निर्माण के लिए हैश, डिस्प्लेस और कंप्रेस एल्गोरिदम का उपयोग किया जा सकता है {{mvar|k}}-तक की अनुमति देकर उत्तम हैश फलन {{mvar|k}} टकराव. इसे पूरा करने के लिए आवश्यक परिवर्तन न्यूनतम हैं, और नीचे अनुकूलित छद्म कोड में रेखांकित किए गए हैं:
एक हैश फ़ंक्शन k-परिपूर्ण होता है यदि S से अधिकतम k तत्वों को श्रेणी में समान मान पर मैप किया जाता है। "हैश, डिस्प्लेस, और कंप्रेस" एल्गोरिदम का उपयोग k संघट्टन की अनुमति देकर k-परफेक्ट हैश फ़ंक्शंस के निर्माण के लिए किया जा सकता है। इसे पूरा करने के लिए आवश्यक परिवर्तन न्यूनतम हैं, और नीचे अनुकूलित छद्म कोड में रेखांकित किए गए हैं:<syntaxhighlight>
(4) सभी के लिए I{{thin space}}∈[r], (2) से क्रम में करें
(4) for all i ∈[r], in the order from (2), do
(5) एल के लिए{{thin space}}←{{thin space}}1,2,...
(5)     for l ← 1,2,...
(6) K बनाते हुए दोहराएँ<sub>i</sub>{{thin space}}←{{thin space}}{{{math|&Phi;}}<sub>l</sub>(x)|x{{thin space}}∈{{thin space}}B<sub>i</sub>}
(6)         repeat forming Ki ← {Φl(x)|x ∈ Bi}
(6) जब तक |के<sub>i</sub>|=|बी<sub>i</sub>| और के<sub>i</sub>∩{j|<u>T[j]=k</u>}={{thin space}}&खाली समुच्चय ;
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=k}= ∅
(7) चलो σ(i):= सफल एल
(7)     let σ(i):= the successful l
(8) सभी जे के लिए{{thin space}}∈{{thin space}}क<sub>i</sub> <u>T[j]←T[j]+1</u> समुच्चय करें
(8)     for all j ∈ Ki set T[j]←T[j]+1
 
</syntaxhighlight>
===आदेश संरक्षण===
===आदेश संरक्षण===
<nowiki>एक न्यूनतम उत्तम हैश फलन {{mvar|F}यदि कुंजियाँ किसी क्रम में दी गई हैं तब } ऑर्डर संरक्षित करना है </nowiki>{{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} और किसी भी कुंजी के लिए {{math|''a''<sub>''j''</sub>}} और {{math|''a''<sub>''k''</sub>}}, {{math|''j'' < ''k''}} तात्पर्य {{math|''F''(''a''<sub>''j''</sub>) < F(''a''<sub>''k''</sub>)}}.<ref>{{Citation |first=Bob |last=Jenkins |contribution=order-preserving minimal perfect hashing |title=Dictionary of Algorithms and Data Structures |editor-first=Paul E. |editor-last=Black |publisher=U.S. National Institute of Standards and Technology |date=14 April 2009 |accessdate=2013-03-05 |url=https://xlinux.nist.gov/dads/HTML/orderPreservMinPerfectHash.html}}</ref> इस मामले में, फलन मान सभी कुंजियों के क्रमबद्ध क्रम में प्रत्येक कुंजी की स्थिति मात्र है। निरंतर पहुंच समय के साथ ऑर्डर-संरक्षित न्यूनतम परफेक्ट हैश फलन का एक सरल कार्यान्वयन प्रत्येक कुंजी की स्थिति की लुकअप तालिका को संग्रहीत करने के लिए एक (सामान्य) परफेक्ट हैश फलन का उपयोग करना है। इस समाधान का उपयोग करता है <math>O(n \log n)</math> बिट्स, जो उस सेटिंग में इष्टतम है जहां कुंजियों के लिए तुलना फलन मनमाना हो सकता है।<ref>{{citation |last1=Fox |first1=Edward A. |title=Order-preserving minimal perfect hash functions and information retrieval |date=July 1991 |url=http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf |journal=ACM Transactions on Information Systems |volume=9 |issue=3 |pages=281–308 |location=New York, NY, USA |publisher=ACM |doi=10.1145/125187.125200 |s2cid=53239140 |last2=Chen |first2=Qi Fan |last3=Daoud |first3=Amjad M. |last4=Heath |first4=Lenwood S.}}.</ref> हालाँकि, यदि चाबियाँ {{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} ब्रह्मांड से निकाले गए पूर्णांक हैं <math>\{1, 2, \ldots, U\}</math>, तब केवल उपयोग करके ऑर्डर-संरक्षित हैश फलन का निर्माण करना संभव है <math>O(n \log \log \log U)</math> जगह के टुकड़े.<ref>{{citation |last1=Belazzougui |first1=Djamal |title=Theory and practice of monotone minimal perfect hashing |date=November 2008 |journal=Journal of Experimental Algorithmics |volume=16 |at=Art. no. 3.2, 26pp |doi=10.1145/1963190.2025378 |s2cid=2367401 |last2=Boldi |first2=Paolo |last3=Pagh |first3=Rasmus |last4=Vigna |first4=Sebastiano |author3-link=Rasmus Pagh}}.</ref> इसके अलावा, यह सीमा इष्टतम मानी जाती है।<ref>{{Citation |last=Assadi |first=Sepehr |title=Tight Bounds for Monotone Minimal Perfect Hashing |date=January 2023 |url=http://dx.doi.org/10.1137/1.9781611977554.ch20 |work=Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=456–476 |access-date=2023-04-27 |place=Philadelphia, PA |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-755-4 |last2=Farach-Colton |first2=Martín |last3=Kuszmaul |first3=William}}</ref>


यदि कुंजियाँ किसी क्रम {{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} में दी गई हैं तो एक न्यूनतम पूर्ण हैश फ़ंक्शन F ऑर्डर संरक्षित है और किसी भी कुंजी {{math|''a''<sub>''j''</sub>}} और {{math|''a''<sub>''k''</sub>}} के लिए, {{math|''j'' < ''k''}} का तात्पर्य {{math|''F''(''a''<sub>''j''</sub>) < F(''a''<sub>''k''</sub>)}} है।<ref>{{Citation |first=Bob |last=Jenkins |contribution=order-preserving minimal perfect hashing |title=Dictionary of Algorithms and Data Structures |editor-first=Paul E. |editor-last=Black |publisher=U.S. National Institute of Standards and Technology |date=14 April 2009 |accessdate=2013-03-05 |url=https://xlinux.nist.gov/dads/HTML/orderPreservMinPerfectHash.html}}</ref> इस स्थिति में, फ़ंक्शन मान सभी कुंजियों के क्रमबद्ध क्रम में प्रत्येक कुंजी की स्थिति मात्र है। निरंतर पहुंच समय के साथ ऑर्डर-संरक्षित न्यूनतम परफेक्ट हैश फ़ंक्शन का एक सरल कार्यान्वयन प्रत्येक कुंजी की स्थिति की लुकअप टेबल को संग्रहीत करने के लिए एक (सामान्य) परफेक्ट हैश फ़ंक्शन का उपयोग करना है। यह समाधान <math>O(n \log n)</math> बिट्स का उपयोग करता है, जो उस सेटिंग में इष्टतम है जहां कुंजियों के लिए तुलना फ़ंक्शन इच्छित हो सकता है।<ref>{{citation |last1=Fox |first1=Edward A. |title=Order-preserving minimal perfect hash functions and information retrieval |date=July 1991 |url=http://eprints.cs.vt.edu/archive/00000248/01/TR-91-01.pdf |journal=ACM Transactions on Information Systems |volume=9 |issue=3 |pages=281–308 |location=New York, NY, USA |publisher=ACM |doi=10.1145/125187.125200 |s2cid=53239140 |last2=Chen |first2=Qi Fan |last3=Daoud |first3=Amjad M. |last4=Heath |first4=Lenwood S.}}.</ref> चूँकि, यदि कुंजियाँ {{math|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} ब्रह्मांड <math>\{1, 2, \ldots, U\}</math> से खींचे गए पूर्णांक हैं, तो केवल <math>O(n \log \log \log U)</math> बिट्स ऑफ़ स्पेस का उपयोग करके ऑर्डर-संरक्षित हैश फ़ंक्शन का निर्माण करना संभव है।<ref>{{citation |last1=Belazzougui |first1=Djamal |title=Theory and practice of monotone minimal perfect hashing |date=November 2008 |journal=Journal of Experimental Algorithmics |volume=16 |at=Art. no. 3.2, 26pp |doi=10.1145/1963190.2025378 |s2cid=2367401 |last2=Boldi |first2=Paolo |last3=Pagh |first3=Rasmus |last4=Vigna |first4=Sebastiano |author3-link=Rasmus Pagh}}.</ref> इसके अतिरिक्त , यह सीमा इष्टतम मानी जाती है।<ref>{{Citation |last=Assadi |first=Sepehr |title=Tight Bounds for Monotone Minimal Perfect Hashing |date=January 2023 |url=http://dx.doi.org/10.1137/1.9781611977554.ch20 |work=Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) |pages=456–476 |access-date=2023-04-27 |place=Philadelphia, PA |publisher=Society for Industrial and Applied Mathematics |isbn=978-1-61197-755-4 |last2=Farach-Colton |first2=Martín |last3=Kuszmaul |first3=William}}</ref>
==संबंधित निर्माण==
==संबंधित निर्माण==


जबकि अच्छी तरह से आकार वाली हैश तालिकाओं में लुकअप, सम्मिलन और विलोपन के लिए औसत O(1) समय (परिशोधित औसत स्थिर समय) होता है, अधिकांश हैश तालिका एल्गोरिदम संभावित सबसे खराब स्थिति वाले समय से ग्रस्त होते हैं जिसमें अधिक समय लगता है।
जबकि अच्छी तरह से आकार वाली हैश तालिकाओं में लुकअप, सम्मिलन और विलोपन के लिए औसत O(1) समय (परिशोधित औसत स्थिर समय) होता है, अधिकांश हैश टेबल एल्गोरिदम संभावित सबसे व्यर्थ स्थिति वाले समय से ग्रस्त होते हैं जिसमें अधिक समय लगता है। सबसे व्यर्थ स्थिति वाला O(1) समय (सबसे व्यर्थ स्थिति में भी स्थिर समय) अनेक अनुप्रयोगों ([[नेटवर्क राउटर]] और [[मेमोरी कैश]] सहित) के लिए परफेक्ट होगा।<ref name="davis" >
सबसे खराब स्थिति वाला O(1) समय (सबसे खराब स्थिति में भी स्थिर समय) अनेक अनुप्रयोगों ([[नेटवर्क राउटर]] और [[मेमोरी कैश]] सहित) के लिए बेहतर होगा।<ref name="davis" >
Timothy A. Davis.
Timothy A. Davis.
[https://www.cs.wm.edu/~tadavis/cs303/ch05sm.pdf "Chapter 5 Hashing"]: subsection "Hash Tables with Worst-Case O(1) Access"
[https://www.cs.wm.edu/~tadavis/cs303/ch05sm.pdf "Chapter 5 Hashing"]: subsection "Hash Tables with Worst-Case O(1) Access"
</ref>{{rp|41}}
</ref>{{rp|41}}


कुछ हैश टेबल एल्गोरिदम सबसे खराब स्थिति O(1) लुकअप समय (सबसे खराब स्थिति में भी निरंतर लुकअप समय) का समर्थन करते हैं। उनमें से कुछ में शामिल हैं: उत्तम हैशिंग; गतिशील उत्तम हैशिंग; [[कोयल हैशिंग]]; [[हॉप्सकॉच हैशिंग]]; और [[विस्तार योग्य हैशिंग]]।<ref name="davis" />{{rp|42-69}}


परफेक्ट हैशिंग का एक सरल विकल्प, जो गतिशील अपडेट की भी अनुमति देता है, कुक्कू हैशिंग है। यह योजना एक सीमा के भीतर दो या दो से अधिक स्थानों की कुंजियों को मानचित्र करती है (परफेक्ट हैशिंग के विपरीत जो प्रत्येक कुंजी को एक ही स्थान पर मानचित्र करती है) लेकिन ऐसा इस तरह से करती है कि कुंजियों को एक-से-एक उन स्थानों पर सौंपा जा सकता है जहां वे हैं मानचित्र किया गया। इस योजना के साथ लुकअप धीमा है, क्योंकि अनेक स्थानों की जाँच की जानी चाहिए, लेकिन फिर भी लगातार सबसे खराब स्थिति में समय लगता है।<ref>{{citation
 
कुछ हैश टेबल एल्गोरिदम सबसे व्यर्थ स्थिति O(1) लुकअप समय (सबसे व्यर्थ स्थिति में भी निरंतर लुकअप समय) का समर्थन करते हैं। उनमें से कुछ में सम्मिलित हैं: परफेक्ट हैशिंग; गतिशील परफेक्ट हैशिंग; [[कोयल हैशिंग]]; [[हॉप्सकॉच हैशिंग]]; और [[विस्तार योग्य हैशिंग]] है ।<ref name="davis" />{{rp|42-69}}
 
परफेक्ट हैशिंग का एक सरल विकल्प, जो गतिशील अपडेट की भी अनुमति देता है, कुक्कू हैशिंग है। यह योजना एक सीमा के अंदर दो या दो से अधिक स्थानों की कुंजियों को मानचित्र करती है (परफेक्ट हैशिंग के विपरीत जो प्रत्येक कुंजी को एक ही स्थान पर मानचित्र करती है) किन्तु ऐसा इस तरह से करती है कि कुंजियों को एक-से-एक उन स्थानों पर सौंपा जा सकता है जहां वे हैं मानचित्र किया गया। इस योजना के साथ लुकअप धीमा है, क्योंकि अनेक स्थानों की जाँच की जानी चाहिए, किन्तु फिर भी निरंतर सबसे व्यर्थ स्थिति में समय लगता है।<ref>{{citation
  | last1 = Pagh | first1 = Rasmus | author1-link = Rasmus Pagh
  | last1 = Pagh | first1 = Rasmus | author1-link = Rasmus Pagh
  | last2 = Rodler | first2 = Flemming Friche
  | last2 = Rodler | first2 = Flemming Friche
Line 182: Line 180:
  | volume = 51
  | volume = 51
  | year = 2004}}.</ref>
  | year = 2004}}.</ref>




Line 207: Line 206:
*[https://github.com/rurban/Perfect-Hash Perfect::Hash], perfect hash generator in Perl that makes C code. Has a "prior art" section worth looking at.
*[https://github.com/rurban/Perfect-Hash Perfect::Hash], perfect hash generator in Perl that makes C code. Has a "prior art" section worth looking at.


{{DEFAULTSORT:Perfect Hash Function}}[[Category: हैशिंग]] [[Category: हैश फ़ंक्शन]] [[Category: एल्गोरिदम खोजें]]
{{DEFAULTSORT:Perfect Hash Function}}
 
 


[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023|Perfect Hash Function]]
[[Category:Created On 10/07/2023]]
[[Category:Lua-based templates|Perfect Hash Function]]
[[Category:Machine Translated Page|Perfect Hash Function]]
[[Category:Pages with script errors|Perfect Hash Function]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Templates Vigyan Ready|Perfect Hash Function]]
[[Category:Templates that add a tracking category|Perfect Hash Function]]
[[Category:Templates that generate short descriptions|Perfect Hash Function]]
[[Category:Templates using TemplateData|Perfect Hash Function]]
[[Category:एल्गोरिदम खोजें|Perfect Hash Function]]
[[Category:हैश फ़ंक्शन|Perfect Hash Function]]
[[Category:हैशिंग|Perfect Hash Function]]

Latest revision as of 12:39, 28 July 2023

दिखाए गए चार नामों के लिए एक आदर्श हैश फ़ंक्शन
दिखाए गए चार नामों के लिए एक न्यूनतम परफेक्ट हैश फ़ंक्शन


कंप्यूटर विज्ञान में, सेट S के लिए एक परफेक्ट हैश फ़ंक्शन h एक हैश फ़ंक्शन है जो S में अलग-अलग तत्वों को m पूर्णांकों के सेट पर बिना किसी संघट्टन के मैप करता है। गणितीय शब्दों में, यह एक इंजेक्शन फ़ंक्शन है।

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

परफेक्ट हैश फ़ंक्शन का हानि यह है कि परफेक्ट हैश फ़ंक्शन के निर्माण के लिए S को जानना आवश्यक है। यदि S बदलता है तो गैर-गतिशील पूर्ण हैश फ़ंक्शंस को फिर से बनाने की आवश्यकता होती है। बार-बार बदलते एस डायनेमिक परफेक्ट हैश फ़ंक्शन के लिए अतिरिक्त स्थान की मूल्य पर उपयोग किया जा सकता है।[1] सही हैश फ़ंक्शन को संग्रहीत करने के लिए स्थान की आवश्यकता O(n) में है।

सही हैश फ़ंक्शंस के लिए महत्वपूर्ण प्रदर्शन पैरामीटर मूल्यांकन समय हैं जो निर्माण समय और प्रतिनिधित्व आकार के अनुरूप होना चाहिए।

आवेदन

फ़ंक्शन के आउटपुट द्वारा अनुक्रमित लुकअप टेबल में S (या अन्य संबंधित मान) से कुंजी रखकर, सीमित सीमा में मानों के साथ एक आदर्श हैश फ़ंक्शन का उपयोग कुशल लुकअप संचालन के लिए किया जा सकता है। इसके बाद कोई यह परीक्षण कर सकता है कि कोई कुंजी S में उपस्थित है या नहीं, या टेबल के सेल में उस कुंजी को देखकर उससे जुड़े मान को देख सकता है। सबसे व्यर्थ स्थिति में ऐसे प्रत्येक लुकअप में निरंतर समय लगता है।[2] सही हैशिंग के साथ, संबंधित डेटा को टेबल तक एकल पहुंच के साथ पढ़ा या लिखा जा सकता है।[3]

परफेक्ट हैश फ़ंक्शंस का प्रदर्शन

सही हैशिंग के लिए महत्वपूर्ण प्रदर्शन पैरामीटर प्रतिनिधित्व आकार, मूल्यांकन समय, निर्माण समय और इसके अतिरिक्त सीमा आवश्यकता हैं।[4] मूल्यांकन का समय O(1) जितना तेज़ हो सकता है, जो इष्टतम है[2][4] निर्माण का समय कम से कम O(n) होना चाहिए, क्योंकि S में प्रत्येक तत्व पर विचार करने की आवश्यकता है, और S में n तत्व सम्मिलित हैं। इस निचली सीमा को वास्तव में प्राप्त किया जा सकता है।[4]


प्रतिनिधित्व आकार की निचली सीमा m और n पर निर्भर करती है। मान लीजिए m = (1+ε) n और h एक आदर्श हैश फ़ंक्शन है। निचली सीमा के लिए एक अच्छा सन्निकटन बिट्स प्रति तत्व है। न्यूनतम पूर्ण हैशिंग के लिए, ε = 0, निचली सीमा log e ≈ 1.44 बिट प्रति तत्व है।[4]

निर्माण

एक विशिष्ट सेट S के लिए एक आदर्श हैश फ़ंक्शन जिसका मूल्यांकन निरंतर समय में किया जा सकता है, और एक छोटी सी सीमा में मूल्यों के साथ, यादृच्छिक एल्गोरिदम द्वारा कई ऑपरेशनों में पाया जा सकता है जो S के आकार के लिए आनुपातिक है। का मूल निर्माण फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) n तत्वों के सेट S को O(n) सूचकांकों की एक श्रृंखला में मैप करने के लिए दो-स्तरीय योजना का उपयोग करते हैं, और फिर प्रत्येक सूचकांक को हैश मानों की एक श्रृंखला में मैप करते हैं। उनके निर्माण का पहला स्तर एक बड़े प्राइम p (ब्रह्मांड के आकार से बड़ा जहां से S खींचा गया है) और एक पैरामीटर k को चुनता है, और S के प्रत्येक तत्व x को सूचकांक में मैप करता है।

यदि k को यादृच्छिक रूप से चुना जाता है, तो इस चरण में संघट्टन होने की संभावना है, किन्तु एक ही सूचकांक i पर एक साथ मैप किए गए तत्वों ni की संख्या छोटी होने की संभावना है। उनके निर्माण का दूसरा स्तर प्रत्येक सूचकांक i के लिए O(ni2) पूर्णांकों की असंयुक्त श्रेणियाँ निर्दिष्ट करता है। यह S के प्रत्येक सदस्य x को g(x) से जुड़ी सीमा में मैप करने के लिए, प्रत्येक सूचकांक i के लिए रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे सेट का उपयोग करता है।[2]

जैसा कि फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) दिखाते हैं, पैरामीटर k का एक विकल्प उपस्थित है जैसे कि g(x) के n विभिन्न मानों के लिए श्रेणियों की लंबाई का योगO(n) है। इसके अतिरिक्त, g(x) के प्रत्येक मान के लिए, एक रैखिक मॉड्यूलर फ़ंक्शन उपस्थित होता है जो S के संबंधित उपसमुच्चय को उस मान से जुड़ी सीमा में मैप करता है। दोनों k, और g(x) के प्रत्येक मान के लिए दूसरे स्तर के फ़ंक्शन, बहुपद समय में मानों को यादृच्छिक रूप से चुनकर तब तक पाए जा सकते हैं जब तक कि कोई कार्य न मिल जाए।[2]

हैश फ़ंक्शन को k, p और सभी दूसरे स्तर के रैखिक मॉड्यूलर फ़ंक्शंस को संग्रहीत करने के लिए संचयन स्थान O(n) की आवश्यकता होती है। किसी दिए गए कुंजी x के हैश मान की गणना निरंतर समय में g(x) की गणना करके, g(x) से जुड़े दूसरे स्तर के फ़ंक्शन को देखकर और इस फ़ंक्शन को x पर प्रयुक्त करके की जा सकती है। शीर्ष स्तर पर बड़ी संख्या में मानों के साथ इस दो-स्तरीय योजना का एक संशोधित संस्करण एक आदर्श हैश फ़ंक्शन के निर्माण के लिए उपयोग किया जा सकता है जो एस को लंबाई n + o(n) की एक छोटी श्रृंखला में मैप करता है।[2]

परफेक्ट हैश फ़ंक्शन के निर्माण के लिए एक और आधुनिक विधि को बेलाज़ौगुई, बोटेल्हो और डिट्ज़फेलबिंगर (2009) ने "हैश, डिस्प्लेस और कंप्रेस" के रूप में वर्णित किया है। यहां प्रथम-स्तरीय हैश फ़ंक्शन g का उपयोग तत्वों को r पूर्णांकों की श्रेणी में मैप करने के लिए भी किया जाता है। एक तत्व xS को बकेट Bg(x) में संग्रहीत किया जाता है।[4]

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

सही हैश फ़ंक्शन h(x) का मूल्यांकन करने के लिए किसी को केवल अनुक्रम में सही हैश फ़ंक्शन पर बकेट इंडेक्स g(x) की मैपिंग σ को सहेजना होगा, जिसके परिणामस्वरूप h(x) = Φσ(g(x)) होगा।[4]

अंत में, प्रतिनिधित्व आकार को कम करने के लिए,σ(i))0 ≤ i < r को एक ऐसे रूप में संपीड़ित किया जाता है जो अभी भी O(1) में मूल्यांकन की अनुमति देता है।[4]

इस दृष्टिकोण को निर्माण के लिए n में रैखिक समय और निरंतर मूल्यांकन समय की आवश्यकता होती है। प्रतिनिधित्व का आकार O(n) में है, और प्राप्त सीमा पर निर्भर करता है। उदाहरण के लिए, m = 1.23n के साथ बेलाज़ौगुई, बोटेल्हो और डाइट्ज़फेलबिंगर (2009) ने 10 मिलियन प्रविष्टियों के अपने दिए गए उदाहरण सेट के लिए 3.03 बिट्स/कुंजी और 1.40 बिट्स/कुंजी के बीच एक प्रतिनिधित्व आकार प्राप्त किया, कम मूल्यों के लिए उच्च गणना समय की आवश्यकता होती है। इस परिदृश्य में निचली सीमा 0.88 बिट/कुंजी है।[4]

छद्मकोड

algorithm hash, displace, and compress is
(1) Split S into buckets Bi := g−1({i})∩S,0 ≤ i < r
(2) Sort buckets Bi in falling order according to size |Bi|
(3) Initialize array T[0...m-1] with 0's
(4) for all i ∈[r], in the order from (2), do
(5)     for l ← 1,2,...
(6)         repeat forming Ki ← {Φl(x)|x ∈ Bi}
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=1}= ∅
(7)     let σ(i):= the successful l
(8)     for all j ∈ Ki let T[j]:= 1
(9) Transform (σi)0≤i<r into compressed form, retaining O(1) access.

अंतरिक्ष निचली सीमा

फ्रेडमैन कोमलोस और ज़ेमेरेडी (1984) के फ़ंक्शन को संग्रहीत करने के लिए जानकारी के O(n) शब्दों का उपयोग लगभग इष्टतम है: किसी भी सही हैश फ़ंक्शन की गणना निरंतर समय में की जा सकती है जिसके लिए कम से कम कई बिट्स की आवश्यकता होती है जो आनुपातिक हो S का आकार का है [5]

न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है

बिट्स/कुंजी.[4]

सही हैश फ़ंक्शंस के लिए, सबसे पहले यह माना जाता है कि की सीमा h से घिरा है n जैसा m = (1+ε) n. द्वारा दिए गए सूत्र के साथ और एक ब्रह्मांड के लिए (गणित) जिसका आकार |U| = u अनंत की ओर जाता है, निचली सीमा में स्थित है

बिट्स/कुंजी, कुल मिलाकर माइनस log(n) बिट्स है।[4]

एक्सटेंशन

मेमोरी एड्रेस पहचान

परफेक्ट हैशिंग का एक तुच्छ किन्तु व्यापक उदाहरण कंप्यूटर की (वर्चुअल) वर्चुअल मेमोरी में निहित है। चूँकि वर्चुअल मेमोरी का प्रत्येक बाइट एक विशिष्ट, अद्वितीय, सीधे पता योग्य संचयन स्थान है, मेमोरी में संग्रहीत (प्रारंभिक) पॉइंटर (कंप्यूटर प्रोग्रामिंग) के मूल्य को संपूर्ण मेमोरी एड्रेस रेंज में उस ऑब्जेक्ट का एक वास्तविक सही हैश माना जा सकता है।[6]


गतिशील परफेक्ट हैशिंग

एक सही हैश फ़ंक्शन का उपयोग करना उन स्थितियों में सबसे अच्छा है जहां बार-बार पूछे जाने वाले बड़े सेट, S, जो संभवतः ही कभी अपडेट किया जाता है। ऐसा इसलिए है क्योंकि सेट S के किसी भी संशोधन के कारण हैश फ़ंक्शन संशोधित सेट के लिए बिल्कुल सही नहीं रह सकता है। ऐसे समाधान जो किसी भी समय सेट को संशोधित करने पर हैश फ़ंक्शन को अपडेट करते हैं, उन्हें डायनेमिक परफेक्ट हैशिंग के रूप में जाना जाता है[1] किन्तु इन विधियों को प्रयुक्त करना अपेक्षाकृत समष्टि है।

न्यूनतम परफेक्ट हैश फ़ंक्शन

न्यूनतम पूर्ण हैश फ़ंक्शन एक पूर्ण हैश फ़ंक्शन है जो n कुंजियों को n निरन्तर पूर्णांकों में मैप करता है - सामान्यतः 0 से n - 1 या 1 से n तक की संख्याएँ है इसे व्यक्त करने का एक अधिक औपचारिक विधि यह है: मान लीजिए कि j और k कुछ परिमित समुच्चय S के तत्व हैं। तब h एक न्यूनतम पूर्ण हैश फ़ंक्शन है यदि और केवल यदि h(j) = h(k) का तात्पर्य j = k(इंजेक्टिविटी) है और एक पूर्णांक a इस प्रकार उपस्थित है कि h का परिसर a..a + |S| − 1 है यह सिद्ध हो चुका है कि एक सामान्य प्रयोजन न्यूनतम परफेक्ट हैश योजना के लिए कम से कम lg e ≈ 1.44 बिट्स/कुंजी की आवश्यकता होती है।[4] यद्यपि यह स्थान सैद्धांतिक कार्यों द्वारा प्राप्त किया गया है, व्यवहार में, सबसे प्रसिद्ध न्यूनतम परफेक्ट हैशिंग योजनाओं के लिए पर्याप्त समय दिए जाने पर लगभग 1.56 बिट्स/कुंजी की आवश्यकता होती है।[7]


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

एक हैश फ़ंक्शन k-परिपूर्ण होता है यदि S से अधिकतम k तत्वों को श्रेणी में समान मान पर मैप किया जाता है। "हैश, डिस्प्लेस, और कंप्रेस" एल्गोरिदम का उपयोग k संघट्टन की अनुमति देकर k-परफेक्ट हैश फ़ंक्शंस के निर्माण के लिए किया जा सकता है। इसे पूरा करने के लिए आवश्यक परिवर्तन न्यूनतम हैं, और नीचे अनुकूलित छद्म कोड में रेखांकित किए गए हैं:

(4) for all i ∈[r], in the order from (2), do
(5)     for l ← 1,2,...
(6)         repeat forming Ki ← {Φl(x)|x ∈ Bi}
(6)         until |Ki|=|Bi| and Ki∩{j|T[j]=k}= ∅
(7)     let σ(i):= the successful l
(8)     for all j ∈ Ki set T[j]←T[j]+1

आदेश संरक्षण

यदि कुंजियाँ किसी क्रम a1, a2, ..., an में दी गई हैं तो एक न्यूनतम पूर्ण हैश फ़ंक्शन F ऑर्डर संरक्षित है और किसी भी कुंजी aj और ak के लिए, j < k का तात्पर्य F(aj) < F(ak) है।[8] इस स्थिति में, फ़ंक्शन मान सभी कुंजियों के क्रमबद्ध क्रम में प्रत्येक कुंजी की स्थिति मात्र है। निरंतर पहुंच समय के साथ ऑर्डर-संरक्षित न्यूनतम परफेक्ट हैश फ़ंक्शन का एक सरल कार्यान्वयन प्रत्येक कुंजी की स्थिति की लुकअप टेबल को संग्रहीत करने के लिए एक (सामान्य) परफेक्ट हैश फ़ंक्शन का उपयोग करना है। यह समाधान बिट्स का उपयोग करता है, जो उस सेटिंग में इष्टतम है जहां कुंजियों के लिए तुलना फ़ंक्शन इच्छित हो सकता है।[9] चूँकि, यदि कुंजियाँ a1, a2, ..., an ब्रह्मांड से खींचे गए पूर्णांक हैं, तो केवल बिट्स ऑफ़ स्पेस का उपयोग करके ऑर्डर-संरक्षित हैश फ़ंक्शन का निर्माण करना संभव है।[10] इसके अतिरिक्त , यह सीमा इष्टतम मानी जाती है।[11]

संबंधित निर्माण

जबकि अच्छी तरह से आकार वाली हैश तालिकाओं में लुकअप, सम्मिलन और विलोपन के लिए औसत O(1) समय (परिशोधित औसत स्थिर समय) होता है, अधिकांश हैश टेबल एल्गोरिदम संभावित सबसे व्यर्थ स्थिति वाले समय से ग्रस्त होते हैं जिसमें अधिक समय लगता है। सबसे व्यर्थ स्थिति वाला O(1) समय (सबसे व्यर्थ स्थिति में भी स्थिर समय) अनेक अनुप्रयोगों (नेटवर्क राउटर और मेमोरी कैश सहित) के लिए परफेक्ट होगा।[12]: 41 


कुछ हैश टेबल एल्गोरिदम सबसे व्यर्थ स्थिति O(1) लुकअप समय (सबसे व्यर्थ स्थिति में भी निरंतर लुकअप समय) का समर्थन करते हैं। उनमें से कुछ में सम्मिलित हैं: परफेक्ट हैशिंग; गतिशील परफेक्ट हैशिंग; कोयल हैशिंग; हॉप्सकॉच हैशिंग; और विस्तार योग्य हैशिंग है ।[12]: 42–69 

परफेक्ट हैशिंग का एक सरल विकल्प, जो गतिशील अपडेट की भी अनुमति देता है, कुक्कू हैशिंग है। यह योजना एक सीमा के अंदर दो या दो से अधिक स्थानों की कुंजियों को मानचित्र करती है (परफेक्ट हैशिंग के विपरीत जो प्रत्येक कुंजी को एक ही स्थान पर मानचित्र करती है) किन्तु ऐसा इस तरह से करती है कि कुंजियों को एक-से-एक उन स्थानों पर सौंपा जा सकता है जहां वे हैं मानचित्र किया गया। इस योजना के साथ लुकअप धीमा है, क्योंकि अनेक स्थानों की जाँच की जानी चाहिए, किन्तु फिर भी निरंतर सबसे व्यर्थ स्थिति में समय लगता है।[13]


संदर्भ

  1. 1.0 1.1 Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Dynamic perfect hashing: upper and lower bounds", SIAM Journal on Computing, 23 (4): 738–761, doi:10.1137/S0097539791194094, MR 1283572.
  2. 2.0 2.1 2.2 2.3 2.4 Fredman, Michael L.; Komlós, János; Szemerédi, Endre (1984), "Storing a Sparse Table with O(1) Worst Case Access Time", Journal of the ACM, 31 (3): 538, doi:10.1145/828.1884, MR 0819156, S2CID 5399743
  3. Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710
  4. 4.00 4.01 4.02 4.03 4.04 4.05 4.06 4.07 4.08 4.09 4.10 4.11 Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794.
  5. Fredman, Michael L.; Komlós, János (1984), "On the size of separating systems and families of perfect hash functions", SIAM Journal on Algebraic and Discrete Methods, 5 (1): 61–68, doi:10.1137/0605009, MR 0731857.
  6. Witold Litwin; Tadeusz Morzy; Gottfried Vossen (19 August 1998). Advances in Databases and Information Systems. Springer Science+Business Media. p. 254. ISBN 9783540649243.
  7. Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Minimal Perfect Hashing via Recursive Splitting", 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Proceedings, pp. 175–185, arXiv:1910.06416, doi:10.1137/1.9781611976007.14.
  8. Jenkins, Bob (14 April 2009), "order-preserving minimal perfect hashing", in Black, Paul E. (ed.), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, retrieved 2013-03-05
  9. Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (July 1991), "Order-preserving minimal perfect hash functions and information retrieval" (PDF), ACM Transactions on Information Systems, New York, NY, USA: ACM, 9 (3): 281–308, doi:10.1145/125187.125200, S2CID 53239140.
  10. Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (November 2008), "Theory and practice of monotone minimal perfect hashing", Journal of Experimental Algorithmics, 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378, S2CID 2367401.
  11. Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (January 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 456–476, ISBN 978-1-61197-755-4, retrieved 2023-04-27
  12. 12.0 12.1 Timothy A. Davis. "Chapter 5 Hashing": subsection "Hash Tables with Worst-Case O(1) Access"
  13. Pagh, Rasmus; Rodler, Flemming Friche (2004), "Cuckoo hashing", Journal of Algorithms, 51 (2): 122–144, doi:10.1016/j.jalgor.2003.12.002, MR 2050140.


अग्रिम पठन


बाहरी संबंध

  • gperf is an Open Source C and C++ perfect hash generator (very fast, but only works for small sets)
  • Minimal Perfect Hashing (bob algorithm) by Bob Jenkins
  • cmph: C Minimal Perfect Hashing Library, open source implementations for many (minimal) perfect hashes (works for big sets)
  • Sux4J: open source monotone minimal perfect hashing in Java
  • MPHSharp: perfect hashing methods in C#
  • BBHash: minimal perfect hash function in header-only C++
  • Perfect::Hash, perfect hash generator in Perl that makes C code. Has a "prior art" section worth looking at.