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

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

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

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

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

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

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