परिभाषा
डायनामिक परफेक्ट हैशिंग को हैश टेबल डेटा संरचना में टकराव को हल करने के लिए एक प्रोग्रामिंग विधि के रूप में परिभाषित किया गया है।
आवेदन
अपने हैश टेबल समकक्षों की तुलना में अधिक मेमोरी-गहन होने पर, यह विधि उन परिस्थितियों के लिए आदर्श है जहां तत्वों के बड़े सेट पर तेज़ क्वेरी, सम्मिलन और विलोपन किया जाना चाहिए।
कार्यान्वयन
डिट्ज़फेलिंगर एट अल। एक गतिशील शब्दकोश एल्गोरिदम की व्याख्या करें कि, जब एम आइटम्स का एक सेट शब्दकोष में वृद्धिशील रूप से जोड़ा जाता है, तो सदस्यता प्रश्न हमेशा निरंतर समय का उपभोग करते हैं और इसलिए ओ (1) सबसे खराब स्थिति का समय होता है, कुल भंडारण की आवश्यकता होती है ओ (एम) (रैखिक), और O(1) अपेक्षित परिशोधन सम्मिलन और विलोपन समय (परिशोधित स्थिर समय)। गतिशील मामले में, जब हैश तालिका में एक कुंजी डाली जाती है, यदि इसकी संबंधित उप तालिका में इसकी प्रविष्टि पर कब्जा कर लिया जाता है, तो एक टकराव का अनुभव होता है और उप तालिका को उसकी नई कुल प्रविष्टि गणना और बेतरतीब ढंग से चुने गए हैश फ़ंक्शन के आधार पर फिर से बनाया गया है। चूंकि दूसरे स्तर की तालिका का लोड फैक्टर कम रहता है, पुनर्निर्माण अक्सर नहीं होता है, और सम्मिलन की परिशोधन अपेक्षित लागत के साथ-साथ हटाने की परिशोधित अपेक्षित लागत ओ (1) है।
इसके अतिरिक्त, शीर्ष-स्तरीय तालिका या किसी भी उप तालिका के अंतिम आकार को गतिशील मामले में कोई पूर्व ज्ञान नहीं है। तालिका के अपेक्षित ओ (एम) स्थान को बनाए रखने के लिए एक तकनीक एक पूर्ण पुनर्निर्माण का संकेत देना है जब पर्याप्त संख्या में सम्मिलन और विलोपन का अनुभव हो। जब तक सम्मिलन या विलोपन की कुल संख्या पिछले निर्माण के समय तत्वों की संख्या से अधिक हो जाती है, तब तक सम्मिलन और विलोपन की परिशोधित अपेक्षित लागत पूर्ण रीहैशिंग पर विचार करके O(1) बनी रहती है।
