स्टैटिक हैशिंग: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
स्थैतिक हैशिंग [[हैश फंकशन|हैश]] समस्या का दूसरा रूप है जो उपयोगकर्ताओं को अंतिम शब्दकोश सेट पर लुकअप करने की अनुमति देता है (शब्दकोश में सभी ऑब्जेक्ट अंतिम हैं और परिवर्तित नहीं हो रहे हैं)। | |||
== उपयोग <ref name="Roche2013">{{cite book | author = Daniel Roche | year = 2013 | title = SI486D: Randomness in Computing, Hashing Unit | publisher = United States Naval Academy, Computer Science Department | url = http://www.usna.edu/Users/cs/roche/courses/s13si486d/u04/#static-and-perfect-hashing| author-link = }}</ref> == | == उपयोग <ref name="Roche2013">{{cite book | author = Daniel Roche | year = 2013 | title = SI486D: Randomness in Computing, Hashing Unit | publisher = United States Naval Academy, Computer Science Department | url = http://www.usna.edu/Users/cs/roche/courses/s13si486d/u04/#static-and-perfect-hashing| author-link = }}</ref> == | ||
=== | ===अनुप्रयोग=== | ||
चूँकि स्टैटिक हैशिंग के लिए आवश्यक है कि [[डेटाबेस]], उसके ऑब्जेक्ट और संदर्भ वही रहें, इसके अनुप्रयोग सीमित हैं। जिन डेटाबेस में ऐसी जानकारी होती है जो | चूँकि स्टैटिक हैशिंग के लिए आवश्यक है कि [[डेटाबेस]], उसके ऑब्जेक्ट और संदर्भ वही रहें, इसके अनुप्रयोग सीमित हैं। जिन डेटाबेस में ऐसी जानकारी होती है जो संभवतः ही कभी परिवर्तित होती है, वे भी पात्र हैं क्योंकि इसके लिए केवल दुर्लभ समय पर पूर्ण डेटाबेस की पूर्ण पुनरावृत्ति की आवश्यकता होगी। इसके उदाहरणों में विशिष्ट भाषाओं के शब्दों और परिभाषाओं के सेट, किसी संगठन के कर्मियों के लिए महत्वपूर्ण डेटा के सेट आदि सम्मिलित हैं। | ||
===उत्तम हैशिंग=== | ===उत्तम हैशिंग=== | ||
परफेक्ट हैशिंग हैशिंग का | परफेक्ट हैशिंग ऐसी हैशिंग का मॉडल है जिसमें n तत्वों के किसी भी सेट को समान आकार की [[हैश तालिका]] में संग्रहीत किया जा सकता है और निरंतर समय में लुकअप किया जा सकता है। इसे विशेष रूप से फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) द्वारा शोध और वर्णन किया गया था और इसलिए इसे एफकेएस हैशिंग उपनाम दिया गया है।<ref name="FKS1984">{{cite book |author1=Michael Fredman |author2=János Komlós |author3=Endre Szemerédi | year = 1984 | title = O(1) वर्स्ट केस एक्सेस टाइम के साथ एक विरल तालिका संग्रहीत करना| publisher = Journal of the ACM (Volume 31, Issue 3) | url = http://dl.acm.org/citation.cfm?id=1884}}</ref> | ||
== एफकेएस हैशिंग == | == एफकेएस हैशिंग == | ||
एफकेएस हैशिंग दो स्तरों के साथ | एफकेएस हैशिंग दो स्तरों के साथ हैश तालिका का उपयोग करता है जिसमें शीर्ष स्तर में n बकेट होते हैं जिनमें प्रत्येक की अपनी हैश तालिका होती है। एफकेएस हैशिंग के लिए आवश्यक है कि यदि हैश विखंडन होता है तो उन्हें ऐसा केवल शीर्ष स्तर पर ही करना होगा। | ||
===कार्यान्वयन=== | ===कार्यान्वयन=== | ||
शीर्ष स्तर में | शीर्ष स्तर में अव्यवस्थित रूप से बनाया गया हैश फ़ंक्शन, h(x) सम्मिलित है, जो कार्टर और वेगमैन हैश फ़ंक्शन की बाधाओं के भीतर फिट बैठता है- जिसे [[यूनिवर्सल हैशिंग]] में देखा जाता है। ऐसा करने के पश्चात शीर्ष स्तर पर k<sub>1</sub>, k<sub>2</sub>, k<sub>3</sub>, ..., k<sub>n</sub> लेबल वाली n बकेट होगी, इस पैटर्न का अनुसरण करते हुए, सभी बकेट में आकार s<sub>i</sub> की हैश तालिका और संबंधित हैश फ़ंक्शन, h<sub>i</sub>(x) होता है। हैश फ़ंक्शन का निर्णय s<sub>i</sub> को k<sub>i</sub><sup>2</sup> पर सेट करके और यादृच्छिक रूप से फ़ंक्शंस के माध्यम से किया जाएगा जब तक कि कोई विखंडन न हो। यह निरंतर समय में किया जा सकता है. | ||
===प्रदर्शन=== | ===प्रदर्शन=== | ||
क्योंकि वहाँ | क्योंकि वहाँ <math>n \choose 2</math>हैं तत्वों के जोड़े, जिनमें टकराव की संभावना 1/n के समान है, एफकेएस हैशिंग n/2 से कम विखंडन की आशा कर सकता है। इस तथ्य के आधार पर और प्रत्येक h(x) का चयन किया गया था जिससे विखंडन की संख्या अधिकतम n/2 हो, निचले स्तर पर प्रत्येक तालिका का आकार 2n से अधिक नहीं होगा। | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 18:58, 18 July 2023
स्थैतिक हैशिंग हैश समस्या का दूसरा रूप है जो उपयोगकर्ताओं को अंतिम शब्दकोश सेट पर लुकअप करने की अनुमति देता है (शब्दकोश में सभी ऑब्जेक्ट अंतिम हैं और परिवर्तित नहीं हो रहे हैं)।
उपयोग [1]
अनुप्रयोग
चूँकि स्टैटिक हैशिंग के लिए आवश्यक है कि डेटाबेस, उसके ऑब्जेक्ट और संदर्भ वही रहें, इसके अनुप्रयोग सीमित हैं। जिन डेटाबेस में ऐसी जानकारी होती है जो संभवतः ही कभी परिवर्तित होती है, वे भी पात्र हैं क्योंकि इसके लिए केवल दुर्लभ समय पर पूर्ण डेटाबेस की पूर्ण पुनरावृत्ति की आवश्यकता होगी। इसके उदाहरणों में विशिष्ट भाषाओं के शब्दों और परिभाषाओं के सेट, किसी संगठन के कर्मियों के लिए महत्वपूर्ण डेटा के सेट आदि सम्मिलित हैं।
उत्तम हैशिंग
परफेक्ट हैशिंग ऐसी हैशिंग का मॉडल है जिसमें n तत्वों के किसी भी सेट को समान आकार की हैश तालिका में संग्रहीत किया जा सकता है और निरंतर समय में लुकअप किया जा सकता है। इसे विशेष रूप से फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) द्वारा शोध और वर्णन किया गया था और इसलिए इसे एफकेएस हैशिंग उपनाम दिया गया है।[2]
एफकेएस हैशिंग
एफकेएस हैशिंग दो स्तरों के साथ हैश तालिका का उपयोग करता है जिसमें शीर्ष स्तर में n बकेट होते हैं जिनमें प्रत्येक की अपनी हैश तालिका होती है। एफकेएस हैशिंग के लिए आवश्यक है कि यदि हैश विखंडन होता है तो उन्हें ऐसा केवल शीर्ष स्तर पर ही करना होगा।
कार्यान्वयन
शीर्ष स्तर में अव्यवस्थित रूप से बनाया गया हैश फ़ंक्शन, h(x) सम्मिलित है, जो कार्टर और वेगमैन हैश फ़ंक्शन की बाधाओं के भीतर फिट बैठता है- जिसे यूनिवर्सल हैशिंग में देखा जाता है। ऐसा करने के पश्चात शीर्ष स्तर पर k1, k2, k3, ..., kn लेबल वाली n बकेट होगी, इस पैटर्न का अनुसरण करते हुए, सभी बकेट में आकार si की हैश तालिका और संबंधित हैश फ़ंक्शन, hi(x) होता है। हैश फ़ंक्शन का निर्णय si को ki2 पर सेट करके और यादृच्छिक रूप से फ़ंक्शंस के माध्यम से किया जाएगा जब तक कि कोई विखंडन न हो। यह निरंतर समय में किया जा सकता है.
प्रदर्शन
क्योंकि वहाँ हैं तत्वों के जोड़े, जिनमें टकराव की संभावना 1/n के समान है, एफकेएस हैशिंग n/2 से कम विखंडन की आशा कर सकता है। इस तथ्य के आधार पर और प्रत्येक h(x) का चयन किया गया था जिससे विखंडन की संख्या अधिकतम n/2 हो, निचले स्तर पर प्रत्येक तालिका का आकार 2n से अधिक नहीं होगा।
यह भी देखें
- हैश फंकशन
- गतिशील उत्तम हैशिंग
संदर्भ
- ↑ Daniel Roche (2013). SI486D: Randomness in Computing, Hashing Unit. United States Naval Academy, Computer Science Department.
- ↑ Michael Fredman; János Komlós; Endre Szemerédi (1984). O(1) वर्स्ट केस एक्सेस टाइम के साथ एक विरल तालिका संग्रहीत करना. Journal of the ACM (Volume 31, Issue 3).
