स्टैटिक हैशिंग

स्थैतिक हैशिंग हैश समस्या का दूसरा रूप है जो उपयोगकर्ताओं को अंतिम शब्दकोश सेट पर लुकअप करने की अनुमति देता है (शब्दकोश में सभी ऑब्जेक्ट अंतिम हैं और परिवर्तित नहीं हो रहे हैं)।

उपयोग

अनुप्रयोग

चूँकि स्टैटिक हैशिंग के लिए आवश्यक है कि डेटाबेस, उसके ऑब्जेक्ट और संदर्भ वही रहें, इसके अनुप्रयोग सीमित हैं। जिन डेटाबेस में ऐसी जानकारी होती है जो संभवतः ही कभी परिवर्तित होती है, वे भी पात्र हैं क्योंकि इसके लिए केवल दुर्लभ समय पर पूर्ण डेटाबेस की पूर्ण पुनरावृत्ति की आवश्यकता होगी। इसके उदाहरणों में विशिष्ट भाषाओं के शब्दों और परिभाषाओं के सेट, किसी संगठन के कर्मियों के लिए महत्वपूर्ण डेटा के सेट आदि सम्मिलित हैं।

उत्तम हैशिंग

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

एफकेएस हैशिंग

एफकेएस हैशिंग दो स्तरों के साथ हैश तालिका का उपयोग करता है जिसमें शीर्ष स्तर में n बकेट होते हैं जिनमें प्रत्येक की अपनी हैश तालिका होती है। एफकेएस हैशिंग के लिए आवश्यक है कि यदि हैश विखंडन होता है तो उन्हें ऐसा केवल शीर्ष स्तर पर ही करना होगा।

कार्यान्वयन

शीर्ष स्तर में अव्यवस्थित रूप से बनाया गया हैश फ़ंक्शन, h(x) सम्मिलित है, जो कार्टर और वेगमैन हैश फ़ंक्शन की बाधाओं के भीतर फिट बैठता है- जिसे यूनिवर्सल हैशिंग में देखा जाता है। ऐसा करने के पश्चात शीर्ष स्तर पर k₁, k₂, k₃, ..., k_n लेबल वाली n बकेट होगी, इस पैटर्न का अनुसरण करते हुए, सभी बकेट में आकार s_i की हैश तालिका और संबंधित हैश फ़ंक्शन, h_i(x) होता है। हैश फ़ंक्शन का निर्णय s_i को k_i² ​​पर सेट करके और यादृच्छिक रूप से फ़ंक्शंस के माध्यम से किया जाएगा जब तक कि कोई विखंडन न हो। यह निरंतर समय में किया जा सकता है.

प्रदर्शन

क्योंकि वहाँ $n \choose 2$हैं तत्वों के जोड़े, जिनमें टकराव की संभावना 1/n के समान है, एफकेएस हैशिंग n/2 से कम विखंडन की आशा कर सकता है। इस तथ्य के आधार पर और प्रत्येक h(x) का चयन किया गया था जिससे विखंडन की संख्या अधिकतम n/2 हो, निचले स्तर पर प्रत्येक तालिका का आकार 2n से अधिक नहीं होगा।

यह भी देखें

• हैश फंकशन
• गतिशील उत्तम हैशिंग