View source for परफेक्ट हैश फ़ंक्शन

{{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 0 0 0 0 0 LL.svg|thumb|240px|right|दिखाए गए चार नामों के लिए एक न्यूनतम उत्तम हैश फ़ंक्शन]][[कंप्यूटर विज्ञान]] में, एक आदर्श हैश फ़ंक्शन {{mvar|h}} एक सेट के लिए {{mvar|S}} एक [[हैश फंकशन]] है जो अलग-अलग तत्वों को मैप करता है {{mvar|S}} के एक सेट के लिए {{mvar|m}} पूर्णांक, बिना किसी हैश टकराव के। गणितीय शब्दों में, यह एक [[इंजेक्शन समारोह]] है।

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

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

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

==आवेदन==
सीमित सीमा में मानों के साथ एक आदर्श हैश फ़ंक्शन का उपयोग कुशल लुकअप संचालन के लिए कुंजी लगाकर किया जा सकता है {{mvar|S}} (या अन्य संबद्ध मान) फ़ंक्शन के आउटपुट द्वारा अनुक्रमित लुकअप तालिका में। इसके बाद कोई यह जांच सकता है कि कोई कुंजी मौजूद है या नहीं {{mvar|S}}, या तालिका के सेल में उस कुंजी की तलाश करके उससे जुड़े मान को देखें। सबसे खराब स्थिति की जटिलता में ऐसे प्रत्येक लुकअप में लगातार समय लगता है।<ref name="inventor"/>सही हैशिंग के साथ, संबंधित डेटा को तालिका तक एकल पहुंच के साथ पढ़ा या लिखा जा सकता है।<ref>{{citation
 | last1 = Lu | first1 = Yi | author1-link = Yi Lu (computer scientist)
 | last2 = Prabhakar | first2 = Balaji | author2-link = Balaji Prabhakar
 | last3 = Bonomi | first3 = Flavio | author3-link = Flavio Bonomi
 | doi = 10.1109/ISIT.2006.261567
 | journal = 2006 IEEE International Symposium on Information Theory
 | pages = 2774–2778
 | title = Perfect Hashing for Network Applications
 | year = 2006| isbn = 1-4244-0505-X | s2cid = 1494710 }}</ref>


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

एक आदर्श हैश फ़ंक्शन के निर्माण के लिए एक और हालिया विधि का वर्णन किया गया है {{harvtxt|Belazzougui|Botelho|Dietzfelbinger|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|''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" />

इस दृष्टिकोण के लिए रैखिक समय की आवश्यकता है {{mvar|n}} निर्माण के लिए, और निरंतर मूल्यांकन समय। प्रतिनिधित्व आकार में है {{math|''O''(''n'')}}, और प्राप्त सीमा पर निर्भर करता है। उदाहरण के लिए, साथ {{math|''m'' {{=}} 1.23''n''}} {{harvtxt|Belazzougui|Botelho|Dietzfelbinger|2009}} ने 10 मिलियन प्रविष्टियों के दिए गए उदाहरण सेट के लिए 3.03 बिट्स/कुंजी और 1.40 बिट्स/कुंजी के बीच एक प्रतिनिधित्व आकार हासिल किया, कम मूल्यों के लिए उच्च गणना समय की आवश्यकता होती है। इस परिदृश्य में निचली सीमा 0.88 बिट/कुंजी है।<ref name="CHD" />
{{missing information|section|RecSplit & "fingerprinting" [https://epubs.siam.org/doi/pdf/10.1137/1.9781611976007.14 recsplit paper]|date=March 2023}}

===छद्मकोड===
 एल्गोरिथम ''हैश, डिस्प्लेस, और कंप्रेस'' है
 (1) एस को बाल्टियों में विभाजित करें {{math|B<sub>i</sub> :{{=}} g<sup>−1</sup>({i})&cap;S,0 ≤ i < r}}
 (2) बाल्टियाँ बी क्रमबद्ध करें<sub>i</sub> आकार के अनुसार घटते क्रम में |बी<sub>i</sub>|
 (3) सरणी T[0...m-1] को 0 से प्रारंभ करें
 (4) सभी के लिए I{{thin space}}∈[r], (2) से क्रम में करें
 (5) एल के लिए{{thin space}}←{{thin space}}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) जब तक |के<sub>i</sub>|=|बी<sub>i</sub>| और के<sub>i</sub>∩{j|T[j]=1}={{thin space}}&खाली सेट;
 (7) चलो σ(i):= सफल एल
 (8) सभी जे के लिए{{thin space}}∈{{thin space}}क<sub>i</sub> चलो टी[जे]:={{thin space}}1
 (9) परिवर्तन (पृ<sub>i</sub>)<sub>0&le;i<r</sub> संपीड़ित रूप में, बनाए रखना {{math|''O''(''1'')}} पहुँच।

==अंतरिक्ष निचली सीमा==
का उपयोग {{math|''O''(''n'')}} कार्य को संग्रहीत करने के लिए जानकारी के शब्द {{harvtxt|Fredman|Komlós|Szemerédi|1984}} लगभग-इष्टतम है: कोई भी पूर्ण हैश फ़ंक्शन जिसकी गणना निरंतर समय में की जा सकती है
के आकार के समानुपाती कम से कम बिट्स की संख्या की आवश्यकता होती है {{mvar|S}}.<ref>{{citation
 | last1 = Fredman | first1 = Michael L. | author1-link = Michael Fredman
 | last2 = Komlós | first2 = János | author2-link = János Komlós (mathematician)
 | doi = 10.1137/0605009
 | issue = 1
 | journal = [[SIAM Journal on Algebraic and Discrete Methods]]
 | mr = 731857
 | pages = 61–68
 | title = On the size of separating systems and families of perfect hash functions
 | volume = 5
 | year = 1984}}.</ref>
न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है
:<math>\log_2e\approx1.44</math>
बिट्स/कुंजी.<ref name="CHD" />

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


===गतिशील उत्तम हैशिंग===
{{main article|Dynamic perfect hashing}}
एक आदर्श हैश फ़ंक्शन का उपयोग करना उन स्थितियों में सबसे अच्छा है जहां बार-बार पूछे जाने वाले बड़े सेट होते हैं, {{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> लेकिन इन तरीकों को लागू करना अपेक्षाकृत जटिल है।

===न्यूनतम उत्तम हैश फ़ंक्शन===
न्यूनतम परफेक्ट हैश फ़ंक्शन एक परफेक्ट हैश फ़ंक्शन है जो मैप करता है {{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
 | 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
 | last2 = Mueller Graf | first2 = Thomas
 | last3 = Vigna | first3 = Sebastiano
 | contribution = RecSplit: Minimal Perfect Hashing via Recursive Splitting
 | doi = 10.1137/1.9781611976007.14
 | pages = 175–185
 | series = [[Proceedings]]
 | title = 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX)
 | year = 2020
 | arxiv = 1910.06416
 | doi-access = free
 }}.</ref>


===k-परफेक्ट हैशिंग===
एक हैश फ़ंक्शन है {{mvar|k}}-यदि अधिक से अधिक हो तो उत्तम {{mvar|k}}तत्वों से {{mvar|S}} को श्रेणी में समान मान पर मैप किया जाता है। निर्माण के लिए हैश, डिस्प्लेस और कंप्रेस एल्गोरिदम का उपयोग किया जा सकता है {{mvar|k}}-तक की अनुमति देकर उत्तम हैश फ़ंक्शन {{mvar|k}} टकराव. इसे पूरा करने के लिए आवश्यक परिवर्तन न्यूनतम हैं, और नीचे अनुकूलित छद्म कोड में रेखांकित किए गए हैं:
 (4) सभी के लिए I{{thin space}}∈[r], (2) से क्रम में करें
 (5) एल के लिए{{thin space}}←{{thin space}}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) जब तक |के<sub>i</sub>|=|बी<sub>i</sub>| और के<sub>i</sub>∩{j|<u>T[j]=k</u>}={{thin space}}&खाली सेट;
 (7) चलो σ(i):= सफल एल
 (8) सभी जे के लिए{{thin space}}∈{{thin space}}क<sub>i</sub> <u>T[j]←T[j]+1</u> सेट करें

===आदेश संरक्षण===
एक न्यूनतम उत्तम हैश फ़ंक्शन {{mvar|F}यदि कुंजियाँ किसी क्रम में दी गई हैं तो } ऑर्डर संरक्षित करना है {{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>


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

जबकि अच्छी तरह से आकार वाली हैश तालिकाओं में लुकअप, सम्मिलन और विलोपन के लिए औसत O(1) समय (परिशोधित औसत स्थिर समय) होता है, अधिकांश हैश तालिका एल्गोरिदम संभावित सबसे खराब स्थिति वाले समय से ग्रस्त होते हैं जिसमें अधिक समय लगता है।
सबसे खराब स्थिति वाला O(1) समय (सबसे खराब स्थिति में भी स्थिर समय) कई अनुप्रयोगों ([[नेटवर्क राउटर]] और [[मेमोरी कैश]] सहित) के लिए बेहतर होगा।<ref name="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"
</ref>{{rp|41}}

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

परफेक्ट हैशिंग का एक सरल विकल्प, जो गतिशील अपडेट की भी अनुमति देता है, कुक्कू हैशिंग है। यह योजना एक सीमा के भीतर दो या दो से अधिक स्थानों की कुंजियों को मैप करती है (परफेक्ट हैशिंग के विपरीत जो प्रत्येक कुंजी को एक ही स्थान पर मैप करती है) लेकिन ऐसा इस तरह से करती है कि कुंजियों को एक-से-एक उन स्थानों पर सौंपा जा सकता है जहां वे हैं मैप किया गया। इस योजना के साथ लुकअप धीमा है, क्योंकि कई स्थानों की जाँच की जानी चाहिए, लेकिन फिर भी लगातार सबसे खराब स्थिति में समय लगता है।<ref>{{citation
 | last1 = Pagh | first1 = Rasmus | author1-link = Rasmus Pagh
 | last2 = Rodler | first2 = Flemming Friche
 | doi = 10.1016/j.jalgor.2003.12.002
 | issue = 2
 | journal = Journal of Algorithms
 | mr = 2050140
 | pages = 122–144
 | title = Cuckoo hashing
 | volume = 51
 | year = 2004}}.</ref>


==संदर्भ==
{{reflist|30em}}


==अग्रिम पठन==
*Richard J. Cichelli. ''Minimal Perfect Hash Functions Made Simple'', Communications of the ACM, Vol. 23, Number 1, January 1980.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'', Third Edition. MIT Press, 2009. {{ISBN|978-0262033848}}. Section 11.5: Perfect hashing, pp.&nbsp;267,&nbsp;277&ndash;282.
* Fabiano C. Botelho, [[Rasmus Pagh]] and Nivio Ziviani. [https://arxiv.org/abs/cs/0702159 "Perfect Hashing for Data Management Applications"].
* Fabiano C. Botelho and [[Nivio Ziviani]]. [http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf "External perfect hashing for very large key sets"]. 16th ACM Conference on Information and Knowledge Management (CIKM07), Lisbon, Portugal, November 2007.
* Djamal Belazzougui, Paolo Boldi, [[Rasmus Pagh]], and Sebastiano Vigna. [https://web.archive.org/web/20140125080021/http://vigna.dsi.unimi.it/ftp/papers/MonotoneMinimalPerfectHashing.pdf "Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses"]. In Proceedings of the 20th Annual ACM-SIAM Symposium On Discrete Mathematics (SODA), New York, 2009. ACM Press.
* Marshall D. Brain and Alan L. Tharp. "Near-perfect Hashing of Large Word Sets". Software—Practice and Experience, vol. 19(10), 967-078, October 1989. John Wiley & Sons.
* Douglas C. Schmidt, [http://www.dre.vanderbilt.edu/~schmidt/PDF/gperf.pdf GPERF: A Perfect Hash Function Generator], C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.


==बाहरी संबंध==
*[https://www.gnu.org/software/gperf/ gperf] is an [[Open Source]] C and C++ perfect hash generator (very fast, but only works for small sets)
*[http://burtleburtle.net/bob/hash/perfect.html Minimal Perfect Hashing (bob algorithm)] by Bob Jenkins
*[http://cmph.sourceforge.net/index.html cmph]: C Minimal Perfect Hashing Library, open source implementations for many (minimal) perfect hashes (works for big sets)
*[http://sux.di.unimi.it/ Sux4J]: open source monotone minimal perfect hashing in Java
*[https://web.archive.org/web/20130729211948/http://www.dupuis.me/node/9 MPHSharp]: perfect hashing methods in C#
*[https://github.com/rizkg/BBHash BBHash]: minimal perfect hash function in header-only C++ 
*[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: एल्गोरिदम खोजें]] 



[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]