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

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

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

कंप्यूटर विज्ञान में, सेट 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 को यादृच्छिक रूप से चुना जाता है, तो इस चरण में संघट्टन होने की संभावना है, किन्तु एक ही सूचकांक i पर एक साथ मैप किए गए तत्वों n_i की संख्या छोटी होने की संभावना है। उनके निर्माण का दूसरा स्तर प्रत्येक सूचकांक i के लिए O(n_i²) पूर्णांकों की असंयुक्त श्रेणियाँ निर्दिष्ट करता है। यह S के प्रत्येक सदस्य x को g(x) से जुड़ी सीमा में मैप करने के लिए, प्रत्येक सूचकांक i के लिए रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे सेट का उपयोग करता है।

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

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

उत्तम हैश फ़ंक्शन के निर्माण के लिए एक और आधुनिक विधि को बेलाज़ौगुई, बोटेल्हो और डिट्ज़फेलबिंगर (2009) ने "हैश, डिस्प्लेस और कंप्रेस" के रूप में वर्णित किया है। यहां प्रथम-स्तरीय हैश फ़ंक्शन 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 के साथ बेलाज़ौगुई, बोटेल्हो और डाइट्ज़फेलबिंगर (2009) ने 10 मिलियन प्रविष्टियों के अपने दिए गए उदाहरण सेट के लिए 3.03 बिट्स/कुंजी और 1.40 बिट्स/कुंजी के बीच एक प्रतिनिधित्व आकार प्राप्त किया, कम मूल्यों के लिए उच्च गणना समय की आवश्यकता होती है। इस परिदृश्य में निचली सीमा 0.88 बिट/कुंजी है।

छद्मकोड

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 का आकार का है

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

$\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-परिपूर्ण होता है यदि 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

आदेश संरक्षण

यदि कुंजियाँ किसी क्रम a₁, a₂, ..., a_n में दी गई हैं तो एक न्यूनतम पूर्ण हैश फ़ंक्शन F ऑर्डर संरक्षित है और किसी भी कुंजी 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.