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

दिखाए गए चार नामों के लिए एक आदर्श हैश फलन

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

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

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

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

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

आवेदन

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

उत्तम हैश फ़ंक्शंस का प्रदर्शन

सही हैशिंग के लिए महत्वपूर्ण प्रदर्शन पैरामीटर प्रतिनिधित्व आकार, मूल्यांकन समय, निर्माण समय और इसके अतिरिक्त सीमा की आवश्यकता हैं ${\frac {m}{n}}$.मूल्यांकन का समय उतना ही तेज़ हो सकता है O(1), जो इष्टतम है.निर्माण का समय कम से कम होना चाहिए O(n), क्योंकि प्रत्येक तत्व में S पर विचार करने की आवश्यकता है, और S रोकना nतत्व. इस निचली सीमा को व्यवहार में हासिल किया जा सकता है।

प्रतिनिधित्व आकार के लिए निचली सीमा निर्भर करती है m और n. होने देना m = (1+ε) n और h एक आदर्श हैश फलन । निचली सीमा के लिए एक अच्छा सन्निकटन है $\log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$ प्रति तत्व बिट्स. न्यूनतम उत्तम हैशिंग के लिए, ε = 0, निचली सीमा है log e ≈ 1.44 प्रति तत्व बिट्स।

निर्माण

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

$g(x)=(kx{\bmod {p}}){\bmod {n}}.$

अगर k को यादृच्छिक रूप से चुना जाता है, इस चरण में टकराव होने की संभावना है, लेकिन तत्वों की संख्या n_i जो एक साथ एक ही सूचकांक पर मानचित्र किए जाते हैं i छोटा होने की संभावना है. उनके निर्माण का दूसरा स्तर असंयुक्त श्रेणियाँ निर्दिष्ट करता है O(n_i²)प्रत्येक सूचकांक के लिए पूर्णांक i. यह रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे समुच्चय का उपयोग करता है, प्रत्येक सूचकांक के लिए एक i, प्रत्येक सदस्य को मानचित्र करने के लिए x का S से जुड़ी सीमा में g(x). जैसा Fredman, Komlós & Szemerédi (1984)दिखाएँ, पैरामीटर का एक विकल्प मौजूद है k जैसे कि श्रेणियों की लंबाई का योग n के विभिन्न मान g(x) है O(n). इसके अतिरिक्त, प्रत्येक मान के लिए g(x), एक रैखिक मॉड्यूलर फलन मौजूद है जो संबंधित उपसमुच्चय को मानचित्र करता है S उस मान से संबद्ध सीमा में। दोनों k, और प्रत्येक मान के लिए दूसरे स्तर के फलन g(x), बहुपद समय में मानों को यादृच्छिक रूप से चुनकर तब तक पाया जा सकता है जब तक कि कोई कार्यशील मान न मिल जाए।

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

एक आदर्श हैश फलन के निर्माण के लिए एक और हालिया विधि का वर्णन किया गया है हैश, डिसप्लेस और कंप्रेस के रूप में। यहां प्रथम-स्तरीय हैश फलन है g का उपयोग तत्वों को किसी श्रेणी में मानचित्र करने के लिए भी किया जाता है r पूर्णांक. तत्व x ∈ S को बाल्टी में संग्रहित किया जाता है B_g(x).

फिर, आकार के घटते क्रम में, प्रत्येक बाल्टी के तत्वों को स्वतंत्र पूर्ण यादृच्छिक हैश फलन के अनुक्रम के हैश फलन द्वारा हैश किया जाता है (Φ₁, Φ₂, Φ₃, ...), प्रारंभ स्थल Φ₁. यदि हैश फलन बकेट के लिए कोई टकराव उत्पन्न नहीं करता है, और परिणामी मान अभी तक अन्य बकेट के अन्य तत्वों द्वारा कब्जा नहीं किया गया है, तब उस बकेट के लिए फलन चुना जाता है। यदि नहीं, तब अनुक्रम में अगले हैश फलन का परीक्षण किया जाता है।

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

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

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

छद्मकोड

एल्गोरिथम हैश, डिस्प्लेस, और कंप्रेस है
(1) एस को बाल्टियों में विभाजित करें Bi := g−1({i})∩S,0 ≤ i < r
(2) बाल्टियाँ बी क्रमबद्ध करेंi आकार के अनुसार घटते क्रम में |बीi|
(3) सरणी T[0...m-1] को 0 से प्रारंभ करें
(4) सभी के लिए I ∈[r], (2) से क्रम में करें
(5) एल के लिए ← 1,2,...
(6) K बनाते हुए दोहराएँi ← {Φl(x)|x ∈ Bi}
(6) जब तक |केi|=|बीi| और केi∩{j|T[j]=1}= &खाली समुच्चय ;
(7) चलो σ(i):= सफल एल
(8) सभी जे के लिए ∈ कi चलो टी[जे]:= 1
(9) परिवर्तन (पृi)0≤i<r संपीड़ित रूप में, बनाए रखना O(1) पहुँच।

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

का उपयोग O(n) कार्य को संग्रहीत करने के लिए जानकारी के शब्द लगभग-इष्टतम है: कोई भी पूर्ण हैश फलन जिसकी गणना निरंतर समय में की जा सकती है के आकार के समानुपाती कम से कम बिट्स की संख्या की आवश्यकता होती है S. न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है

$\log _{2}e\approx 1.44$

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

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

$\log _{2}e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$

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

एक्सटेंशन

मेमोरी पता पहचान

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

गतिशील उत्तम हैशिंग

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

न्यूनतम उत्तम हैश फलन

न्यूनतम परफेक्ट हैश फलन एक परफेक्ट हैश फलन है जो मानचित्र करता है 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 बिट्स/कुंजी। यद्यपि यह स्थान सैद्धांतिक कार्यों द्वारा हासिल किया गया है, व्यवहार में, सबसे प्रसिद्ध न्यूनतम सही हैशिंग योजनाओं को पर्याप्त समय दिए जाने पर लगभग 1.56 बिट्स/कुंजी की आवश्यकता होती है।

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

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

(4) सभी के लिए I ∈[r], (2) से क्रम में करें
(5) एल के लिए ← 1,2,...
(6) K बनाते हुए दोहराएँi ← {Φl(x)|x ∈ Bi}
(6) जब तक |केi|=|बीi| और केi∩{j|T[j]=k}= &खाली समुच्चय ;
(7) चलो σ(i):= सफल एल
(8) सभी जे के लिए ∈ कi T[j]←T[j]+1 समुच्चय करें

आदेश संरक्षण

एक न्यूनतम उत्तम हैश फलन {{mvar|F}यदि कुंजियाँ किसी क्रम में दी गई हैं तब } ऑर्डर संरक्षित करना है a₁, a₂, ..., a_n और किसी भी कुंजी के लिए a_j और a_k, j < k तात्पर्य F(a_j) < F(a_k). इस मामले में, फलन मान सभी कुंजियों के क्रमबद्ध क्रम में प्रत्येक कुंजी की स्थिति मात्र है। निरंतर पहुंच समय के साथ ऑर्डर-संरक्षित न्यूनतम परफेक्ट हैश फलन का एक सरल कार्यान्वयन प्रत्येक कुंजी की स्थिति की लुकअप तालिका को संग्रहीत करने के लिए एक (सामान्य) परफेक्ट हैश फलन का उपयोग करना है। इस समाधान का उपयोग करता है $O(n\log n)$ बिट्स, जो उस सेटिंग में इष्टतम है जहां कुंजियों के लिए तुलना फलन मनमाना हो सकता है। हालाँकि, यदि चाबियाँ a₁, a₂, ..., a_n ब्रह्मांड से निकाले गए पूर्णांक हैं $\{1,2,\ldots ,U\}$, तब केवल उपयोग करके ऑर्डर-संरक्षित हैश फलन का निर्माण करना संभव है $O(n\log \log \log U)$ जगह के टुकड़े. इसके अलावा, यह सीमा इष्टतम मानी जाती है।

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

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

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

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

अग्रिम पठन

• 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. 267, 277–282.
• Fabiano C. Botelho, Rasmus Pagh and Nivio Ziviani. "Perfect Hashing for Data Management Applications".
• Fabiano C. Botelho and Nivio Ziviani. "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. "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, GPERF: A Perfect Hash Function Generator, C++ Report, SIGS, Vol. 10, No. 10, November/December, 1998.

बाहरी संबंध

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