स्टैटिक हैशिंग: Difference between revisions
(Created page with "स्टेटिक हैशिंग हैश फंकशन समस्या का दूसरा रूप है जो उपयोगकर्ताओं...") |
No edit summary |
||
| Line 7: | Line 7: | ||
===उत्तम हैशिंग=== | ===उत्तम हैशिंग=== | ||
परफेक्ट हैशिंग हैशिंग का | परफेक्ट हैशिंग हैशिंग का मॉडल है जिसमें 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> | ||
== एफकेएस हैशिंग == | |||
==एफकेएस हैशिंग== | एफकेएस हैशिंग दो स्तरों के साथ हैश तालिका का उपयोग करता है जिसमें शीर्ष स्तर में एन बकेट होते हैं जिनमें प्रत्येक की अपनी हैश तालिका होती है। एफकेएस हैशिंग के लिए आवश्यक है कि यदि हैश टकराव होता है तो उन्हें ऐसा केवल शीर्ष स्तर पर ही करना होगा। | ||
एफकेएस हैशिंग दो स्तरों के साथ | |||
===कार्यान्वयन=== | ===कार्यान्वयन=== | ||
शीर्ष स्तर में | शीर्ष स्तर में बेतरतीब ढंग से बनाया गया हैश फ़ंक्शन, h(x) शामिल है, जो कार्टर और वेगमैन हैश फ़ंक्शन की बाधाओं के भीतर फिट बैठता है - जिसे [[यूनिवर्सल हैशिंग]] में देखा जाता है। ऐसा करने पर शीर्ष स्तर पर k लेबल वाली n बाल्टियाँ होंगी<sub>1</sub>, क<sub>2</sub>, क<sub>3</sub>, ..., क<sub>n</sub>. इस पैटर्न का अनुसरण करते हुए, सभी बाल्टियाँ आकार s की हैश तालिका रखती हैं<sub>i</sub> और संबंधित हैश फ़ंक्शन, एच<sub>i</sub>(्स)। हैश फ़ंक्शन सेटिंग्स द्वारा तय किया जाएगा<sub>i</sub> से क<sub>i</sub><sup>2</sup>और बेतरतीब ढंग से कार्यों से गुजरना जब तक कि कोई टकराव न हो। यह निरंतर समय में किया जा सकता है. | ||
===प्रदर्शन=== | ===प्रदर्शन=== | ||
Revision as of 18:43, 18 July 2023
स्टेटिक हैशिंग हैश फंकशन समस्या का दूसरा रूप है जो उपयोगकर्ताओं को अंतिम शब्दकोश सेट पर लुकअप करने की अनुमति देता है (शब्दकोश में सभी ऑब्जेक्ट अंतिम हैं और बदल नहीं रहे हैं)।
उपयोग [1]
आवेदन
चूँकि स्टैटिक हैशिंग के लिए आवश्यक है कि डेटाबेस, उसके ऑब्जेक्ट और संदर्भ वही रहें, इसके अनुप्रयोग सीमित हैं। जिन डेटाबेस में ऐसी जानकारी होती है जो शायद ही कभी बदलती है, वे भी पात्र हैं क्योंकि इसके लिए केवल दुर्लभ अवसर पर पूरे डेटाबेस की पूर्ण पुनरावृत्ति की आवश्यकता होगी। इसके उदाहरणों में विशिष्ट भाषाओं के शब्दों और परिभाषाओं के सेट, किसी संगठन के कर्मियों के लिए महत्वपूर्ण डेटा के सेट आदि शामिल हैं।
उत्तम हैशिंग
परफेक्ट हैशिंग हैशिंग का मॉडल है जिसमें n तत्वों के किसी भी सेट को समान आकार की हैश तालिका में संग्रहीत किया जा सकता है और निरंतर समय में लुकअप किया जा सकता है। इसे विशेष रूप से फ्रेडमैन, कोमलोस और ज़ेमेरेडी (1984) द्वारा खोजा और चर्चा की गई थी और इसलिए इसे एफकेएस हैशिंग उपनाम दिया गया है।[2]
एफकेएस हैशिंग
एफकेएस हैशिंग दो स्तरों के साथ हैश तालिका का उपयोग करता है जिसमें शीर्ष स्तर में एन बकेट होते हैं जिनमें प्रत्येक की अपनी हैश तालिका होती है। एफकेएस हैशिंग के लिए आवश्यक है कि यदि हैश टकराव होता है तो उन्हें ऐसा केवल शीर्ष स्तर पर ही करना होगा।
कार्यान्वयन
शीर्ष स्तर में बेतरतीब ढंग से बनाया गया हैश फ़ंक्शन, h(x) शामिल है, जो कार्टर और वेगमैन हैश फ़ंक्शन की बाधाओं के भीतर फिट बैठता है - जिसे यूनिवर्सल हैशिंग में देखा जाता है। ऐसा करने पर शीर्ष स्तर पर k लेबल वाली n बाल्टियाँ होंगी1, क2, क3, ..., कn. इस पैटर्न का अनुसरण करते हुए, सभी बाल्टियाँ आकार s की हैश तालिका रखती हैंi और संबंधित हैश फ़ंक्शन, एचi(्स)। हैश फ़ंक्शन सेटिंग्स द्वारा तय किया जाएगाi से कi2और बेतरतीब ढंग से कार्यों से गुजरना जब तक कि कोई टकराव न हो। यह निरंतर समय में किया जा सकता है.
प्रदर्शन
क्योंकि वहाँ हैं तत्वों के जोड़े, जिनमें टकराव की संभावना 1/एन के बराबर है, एफकेएस हैशिंग एन/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).
