स्टैटिक हैशिंग
स्टेटिक हैशिंग हैश फंकशन समस्या का दूसरा रूप है जो उपयोगकर्ताओं को अंतिम शब्दकोश सेट पर लुकअप करने की अनुमति देता है (शब्दकोश में सभी ऑब्जेक्ट अंतिम हैं और बदल नहीं रहे हैं)।
उपयोग [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).
