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

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

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

कंप्यूटर विज्ञान में, एक आदर्श हैश फ़ंक्शन 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).

एक आदर्श हैश फ़ंक्शन के निर्माण के लिए एक और हालिया विधि का वर्णन किया गया है Belazzougui, Botelho & Dietzfelbinger (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 Belazzougui, Botelho & Dietzfelbinger (2009) ने 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) कार्य को संग्रहीत करने के लिए जानकारी के शब्द Fredman, Komlós & Szemerédi (1984) लगभग-इष्टतम है: कोई भी पूर्ण हैश फ़ंक्शन जिसकी गणना निरंतर समय में की जा सकती है के आकार के समानुपाती कम से कम बिट्स की संख्या की आवश्यकता होती है S. न्यूनतम पूर्ण हैश फ़ंक्शंस के लिए सूचना सैद्धांतिक स्थान निचली सीमा है

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

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

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

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

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

एक्सटेंशन

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

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

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

Main article: Dynamic perfect hashing

एक आदर्श हैश फ़ंक्शन का उपयोग करना उन स्थितियों में सबसे अच्छा है जहां बार-बार पूछे जाने वाले बड़े सेट होते हैं, 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.