परफेक्ट हैशिंग की परिभाषा (Definition of Perfect Hashing)
परफेक्ट हैशिंग (Perfect Hashing) को हैशिंग के एक मॉडल के रूप में परिभाषित किया जाता है जिसमें n एलिमेंट्स के किसी भी सेट को समान आकार के हैश टेबल (Hash Table) में स्टोर किया जा सकता है और कॉन्स्टेंट समय में लुकअप (Lookups) किए जा सकते हैं। इसे विशेष रूप से फ्रेडमैन, कोमलोस और स्ज़ेमेरेदी (Fredman, Komlos and Szemeredi) (1984) द्वारा आविष्कृत और चर्चा की गई थी और इसलिए इसे "FKS हैशिंग" (FKS Hashing) उपनाम दिया गया है।
स्टेटिक हैशिंग की परिभाषा (Definition of Static Hashing)
स्टेटिक हैशिंग (Static Hashing) हैशिंग समस्या का एक और रूप परिभाषित करता है जो यूज़र्स को फाइनलाइज़्ड डिक्शनरी सेट (Finalized Dictionary Set) पर लुकअप करने की अनुमति देता है (यानी डिक्शनरी में सभी ऑब्जेक्ट अंतिम हैं और साथ ही बदल नहीं रहे हैं)।
अनुप्रयोग (Application)
चूंकि स्टेटिक हैशिंग के लिए आवश्यक है कि डेटाबेस, इसके ऑब्जेक्ट्स और रेफरेंस समान रहें, इसके अनुप्रयोग सीमित हैं। डेटाबेस जिनमें ऐसी जानकारी होती है जो शायद ही कभी बदलती है, वे भी पात्र हैं क्योंकि इसके लिए केवल दुर्लभ अवसर पर पूरे डेटाबेस के पूर्ण रीहैश (Full Rehash) की आवश्यकता होगी। इस हैशिंग स्कीम के विभिन्न उदाहरणों में विशिष्ट भाषाओं के शब्दों और परिभाषाओं के सेट, किसी संगठन के कर्मियों के लिए महत्वपूर्ण डेटा के सेट आदि शामिल हैं।
कार्यान्वयन (Implementation)
स्टेटिक मामले में, हमें समय से पहले कुल p एंट्रीज़ का एक सेट प्रदान किया जाता है, प्रत्येक एक यूनिक कुंजी से जुड़ा होता है। फ्रेडमैन, कोमलोस और स्ज़ेमेरेदी आकार s = 2(p-1) बकेट्स के साथ फर्स्ट-लेवल हैश टेबल चुनते हैं। निर्माण के लिए, p एंट्रीज़ को टॉप-लेवल हैशिंग फंक्शन द्वारा q बकेट्स में अलग किया जाता है, जहां q = 2(p-1)। फिर r एंट्रीज़ वाले प्रत्येक बकेट के लिए, r² स्लॉट्स के साथ सेकंड-लेवल टेबल आवंटित की जाती है, और इसका हैश फंक्शन यूनिवर्सल हैश फंक्शन सेट (Universal Hash Function Set) से रैंडमली चुना जाता है ताकि यह टकराव-मुक्त (Collision-free) हो जाए और हैश टेबल के साथ स्टोर किया जाए। यदि रैंडमली चुना गया हैश फंक्शन टकराव वाली टेबल बनाता है, तो एक नया हैश फंक्शन रैंडमली चुना जाता है जब तक कि टकराव-मुक्त टेबल की गारंटी न हो जाए। अंत में, टकराव-मुक्त हैश के साथ, r एंट्रीज़ को सेकंड-लेवल टेबल में हैश किया जाता है।
