परिभाषा (Definition)
डायनामिक परफेक्ट हैशिंग (Dynamic Perfect Hashing) को हैश टेबल डेटा स्ट्रक्चर में टकराव (Collisions) हल करने के लिए एक प्रोग्रामिंग मेथड के रूप में परिभाषित किया जाता है।
अनुप्रयोग (Application)
अपने हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-गहन (Memory-intensive) होने के बावजूद, यह मेथड उन स्थितियों के लिए आदर्श है जहां बड़ी संख्या में एलिमेंट्स पर तेज़ क्वेरीज़, सम्मिलन, और विलोपन किए जाने चाहिए।
कार्यान्वयन (Implementation)
डायट्ज़फेलबिंगर एट अल (Dietzfelbinger et al.) एक डायनामिक डिक्शनरी एल्गोरिदम (Dynamic Dictionary Algorithm) समझाते हैं जो, जब m आइटम्स का एक सेट डिक्शनरी में वृद्धिशील रूप से जोड़ा जाता है, सदस्यता क्वेरीज़ (Membership Queries) हमेशा कॉन्स्टेंट समय लेती हैं और इसलिए O(1) सबसे खराब स्थिति समय, कुल आवश्यक स्टोरेज O(m) (रैखिक) है, और O(1) अपेक्षित परिशोधित सम्मिलन और विलोपन समय (Amortized Constant Time)। डायनामिक मामले में, जब एक कुंजी हैश टेबल में डाली जाती है, यदि इसकी एंट्री इसके संबंधित सब-टेबल में कब्जा है, तो टकराव अनुभव होता है और सब-टेबल को इसके नए कुल एंट्री काउंट और रैंडमली चुने गए हैश फंक्शन के आधार पर पुनर्निर्मित (Rebuilt) किया जाता है। क्योंकि सेकंड-लेवल टेबल का लोड फैक्टर (Load Factor) कम रखा जाता है, पुनर्निर्माण बार-बार नहीं होता, और सम्मिलन के साथ-साथ विलोपन की परिशोधित अपेक्षित लागत O(1) है।
इसके अतिरिक्त, डायनामिक मामले में टॉप-लेवल टेबल या किसी सब-टेबल के अंतिम आकार का कोई पूर्व ज्ञान नहीं है। टेबल के अपेक्षित O(m) स्पेस को बनाए रखने के लिए एक तकनीक यह है कि जब पर्याप्त संख्या में सम्मिलन और विलोपन हो जाएं तो पूर्ण पुनर्निर्माण (Full Rebuilding) को प्रेरित किया जाए। जब तक सम्मिलन या विलोपन की कुल संख्या अंतिम निर्माण के समय एलिमेंट्स की संख्या से अधिक हो जाती है, तब तक पूर्ण रीहैशिंग (Full Rehashing) पर विचार करके सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत O(1) रहती है।
