परफेक्ट हैश फ़ंक्शन: Difference between revisions

Latest revision as of 12:39, 28 July 2023

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

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

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

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

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

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

आवेदन

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

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

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

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

निर्माण

एक विशिष्ट सेट $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 2)$ पूर्णांकों की असंयुक्त श्रेणियाँ निर्दिष्ट करता है। यह $S$ के प्रत्येक सदस्य $x$ को $g (x)$ से जुड़ी सीमा में मैप करने के लिए, प्रत्येक सूचकांक $i$ के लिए रैखिक मॉड्यूलर फ़ंक्शंस के दूसरे सेट का उपयोग करता है।^[2]

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

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

परफेक्ट हैश फ़ंक्शन के निर्माण के लिए एक और आधुनिक विधि को बेलाज़ौगुई, बोटेल्हो और डिट्ज़फेलबिंगर (2009) ने "हैश, डिस्प्लेस और कंप्रेस" के रूप में वर्णित किया है। यहां प्रथम-स्तरीय हैश फ़ंक्शन $g$ का उपयोग तत्वों को $r$ पूर्णांकों की श्रेणी में मैप करने के लिए भी किया जाता है। एक तत्व $x \in S$ को बकेट $B g(x)$ में संग्रहीत किया जाता है।^[4]

फिर, आकार के घटते क्रम में, प्रत्येक बकेट के तत्वों को $Φ 1$ से प्रारंभ करके स्वतंत्र पूर्ण यादृच्छिक हैश फ़ंक्शन $(Φ 1, Φ 2, Φ 3, ...)$ के अनुक्रम के हैश फ़ंक्शन द्वारा हैश किया जाता है। यदि हैश फ़ंक्शन बकेट के लिए कोई संघट्टन उत्पन्न नहीं करता है, और परिणामी मान अभी तक अन्य बकेट के अन्य तत्वों द्वारा अधिकृत नहीं किया गया है, तो उस बकेट के लिए फ़ंक्शन चुना जाता है। यदि नहीं, तो अनुक्रम में अगले हैश फ़ंक्शन का परीक्षण किया जाता है।^[4]

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

अंत में, प्रतिनिधित्व आकार को कम करने के लिए, $σ(i)) 0 \leq i < r$ को एक ऐसे रूप में संपीड़ित किया जाता है जो अभी भी $O (1)$ में मूल्यांकन की अनुमति देता है।^[4]

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

छद्मकोड

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$ का आकार का है ^[5]

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

\log _{2}e\approx 1.44

बिट्स/कुंजी.^[4]

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

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

बिट्स/कुंजी, कुल मिलाकर माइनस $log(n)$ बिट्स है।^[4]

एक्सटेंशन

मेमोरी एड्रेस पहचान

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

गतिशील परफेक्ट हैशिंग

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

न्यूनतम परफेक्ट हैश फ़ंक्शन

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

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 1, a 2, ..., a n$ में दी गई हैं तो एक न्यूनतम पूर्ण हैश फ़ंक्शन F ऑर्डर संरक्षित है और किसी भी कुंजी $a j$ और $a k$ के लिए, $j < k$ का तात्पर्य $F (a j) < F(a k)$ है।^[8] इस स्थिति में, फ़ंक्शन मान सभी कुंजियों के क्रमबद्ध क्रम में प्रत्येक कुंजी की स्थिति मात्र है। निरंतर पहुंच समय के साथ ऑर्डर-संरक्षित न्यूनतम परफेक्ट हैश फ़ंक्शन का एक सरल कार्यान्वयन प्रत्येक कुंजी की स्थिति की लुकअप टेबल को संग्रहीत करने के लिए एक (सामान्य) परफेक्ट हैश फ़ंक्शन का उपयोग करना है। यह समाधान $O(n\log n)$ बिट्स का उपयोग करता है, जो उस सेटिंग में इष्टतम है जहां कुंजियों के लिए तुलना फ़ंक्शन इच्छित हो सकता है।^[9] चूँकि, यदि कुंजियाँ $a 1, a 2, ..., a n$ ब्रह्मांड $\{1,2,\ldots ,U\}$ से खींचे गए पूर्णांक हैं, तो केवल $O(n\log \log \log U)$ बिट्स ऑफ़ स्पेस का उपयोग करके ऑर्डर-संरक्षित हैश फ़ंक्शन का निर्माण करना संभव है।^[10] इसके अतिरिक्त , यह सीमा इष्टतम मानी जाती है।^[11]

संदर्भ

↑ ^1.0 ^1.1 Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Dynamic perfect hashing: upper and lower bounds", SIAM Journal on Computing, 23 (4): 738–761, doi:10.1137/S0097539791194094, MR 1283572.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 Fredman, Michael L.; Komlós, János; Szemerédi, Endre (1984), "Storing a Sparse Table with $O (1)$ Worst Case Access Time", Journal of the ACM, 31 (3): 538, doi:10.1145/828.1884, MR 0819156, S2CID 5399743
↑ Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710
↑ ^4.00 ^4.01 ^4.02 ^4.03 ^4.04 ^4.05 ^4.06 ^4.07 ^4.08 ^4.09 ^4.10 ^4.11 Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794.
↑ Fredman, Michael L.; Komlós, János (1984), "On the size of separating systems and families of perfect hash functions", SIAM Journal on Algebraic and Discrete Methods, 5 (1): 61–68, doi:10.1137/0605009, MR 0731857.
↑ Witold Litwin; Tadeusz Morzy; Gottfried Vossen (19 August 1998). Advances in Databases and Information Systems. Springer Science+Business Media. p. 254. ISBN 9783540649243.
↑ Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Minimal Perfect Hashing via Recursive Splitting", 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Proceedings, pp. 175–185, arXiv:1910.06416, doi:10.1137/1.9781611976007.14.
↑ Jenkins, Bob (14 April 2009), "order-preserving minimal perfect hashing", in Black, Paul E. (ed.), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, retrieved 2013-03-05
↑ Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (July 1991), "Order-preserving minimal perfect hash functions and information retrieval" (PDF), ACM Transactions on Information Systems, New York, NY, USA: ACM, 9 (3): 281–308, doi:10.1145/125187.125200, S2CID 53239140.
↑ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (November 2008), "Theory and practice of monotone minimal perfect hashing", Journal of Experimental Algorithmics, 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378, S2CID 2367401.
↑ Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (January 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 456–476, ISBN 978-1-61197-755-4, retrieved 2023-04-27
↑ ^12.0 ^12.1 Timothy A. Davis. "Chapter 5 Hashing": subsection "Hash Tables with Worst-Case O(1) Access"
↑ Pagh, Rasmus; Rodler, Flemming Friche (2004), "Cuckoo hashing", Journal of Algorithms, 51 (2): 122–144, doi:10.1016/j.jalgor.2003.12.002, MR 2050140.

अग्रिम पठन

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.

[DynamicPerfectHashing-1] 1.0 ^1.1 Dietzfelbinger, Martin; Karlin, Anna; Mehlhorn, Kurt; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Dynamic perfect hashing: upper and lower bounds", SIAM Journal on Computing, 23 (4): 738–761, doi:10.1137/S0097539791194094, MR 1283572.

[inventor-2] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 Fredman, Michael L.; Komlós, János; Szemerédi, Endre (1984), "Storing a Sparse Table with $O (1)$ Worst Case Access Time", Journal of the ACM, 31 (3): 538, doi:10.1145/828.1884, MR 0819156, S2CID 5399743

[3] Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710

[CHD-4] 4.00 ^4.01 ^4.02 ^4.03 ^4.04 ^4.05 ^4.06 ^4.07 ^4.08 ^4.09 ^4.10 ^4.11 Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794.

[5] Fredman, Michael L.; Komlós, János (1984), "On the size of separating systems and families of perfect hash functions", SIAM Journal on Algebraic and Discrete Methods, 5 (1): 61–68, doi:10.1137/0605009, MR 0731857.

[6] Witold Litwin; Tadeusz Morzy; Gottfried Vossen (19 August 1998). Advances in Databases and Information Systems. Springer Science+Business Media. p. 254. ISBN 9783540649243.

[RecSplit-7] Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Minimal Perfect Hashing via Recursive Splitting", 2020 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), Proceedings, pp. 175–185, arXiv:1910.06416, doi:10.1137/1.9781611976007.14.

[8] Jenkins, Bob (14 April 2009), "order-preserving minimal perfect hashing", in Black, Paul E. (ed.), Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, retrieved 2013-03-05

[9] Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (July 1991), "Order-preserving minimal perfect hash functions and information retrieval" (PDF), ACM Transactions on Information Systems, New York, NY, USA: ACM, 9 (3): 281–308, doi:10.1145/125187.125200, S2CID 53239140.

[10] Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (November 2008), "Theory and practice of monotone minimal perfect hashing", Journal of Experimental Algorithmics, 16, Art. no. 3.2, 26pp, doi:10.1145/1963190.2025378, S2CID 2367401.

[11] Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (January 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Philadelphia, PA: Society for Industrial and Applied Mathematics, pp. 456–476, ISBN 978-1-61197-755-4, retrieved 2023-04-27

[davis-12] 12.0 ^12.1 Timothy A. Davis. "Chapter 5 Hashing": subsection "Hash Tables with Worst-Case O(1) Access"

[13] Pagh, Rasmus; Rodler, Flemming Friche (2004), "Cuckoo hashing", Journal of Algorithms, 51 (2): 122–144, doi:10.1016/j.jalgor.2003.12.002, MR 2050140.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

Anonymous

Search

परफेक्ट हैश फ़ंक्शन: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 12:39, 28 July 2023

Contents

आवेदन

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