সংজ্ঞা
ডায়নামিক নিখুঁত হ্যাশিং একটি হ্যাশ টেবিল ডেটা স্ট্রাকচারে সংঘর্ষের সমাধান করার জন্য একটি প্রোগ্রামিং পদ্ধতি হিসাবে সংজ্ঞায়িত করা হয়৷
আবেদন
যদিও এর হ্যাশ টেবিলের প্রতিরূপের তুলনায় অনেক বেশি মেমরি-নিবিড়, এই পদ্ধতিটি এমন পরিস্থিতিতে আদর্শ যেখানে দ্রুত ক্যোয়ারী, সন্নিবেশ, এবং মুছে ফেলা আবশ্যক উপাদানগুলির একটি বড় সেটে সঞ্চালিত হতে হবে।
বাস্তবায়ন
Dietzfelbinger et al. একটি গতিশীল অভিধান অ্যালগরিদম ব্যাখ্যা করুন যে, যখন m আইটেমগুলির একটি সেট ক্রমবর্ধমানভাবে অভিধানে যুক্ত করা হয়, সদস্যপদ প্রশ্নগুলি সর্বদা ধ্রুবক সময় ব্যয় করে এবং সেইজন্য O(1) সবচেয়ে খারাপ-কেস সময়, প্রয়োজনীয় মোট স্টোরেজ হল O(m) (লিনিয়ার), এবং O(1) প্রত্যাশিত পরিমার্জিত সন্নিবেশ এবং মুছে ফেলার সময় (অমর্টাইজড ধ্রুবক সময়)। ডায়নামিক ক্ষেত্রে, যখন হ্যাশ টেবিলে একটি কী ঢোকানো হয়, যদি তার নিজ নিজ সাব টেবিলে এর এন্ট্রি দখল করা হয়, তাহলে একটি সংঘর্ষের অভিজ্ঞতা হয় এবং সাব টেবিলটি নতুন মোট প্রবেশের সংখ্যা এবং এলোমেলোভাবে নির্বাচিত হ্যাশ ফাংশনের উপর ভিত্তি করে পুনর্নির্মাণ করা হয়েছে। যেহেতু দ্বিতীয়-স্তরের টেবিলের লোড ফ্যাক্টর কম থাকে, পুনঃনির্মাণ ঘন ঘন হয় না, এবং সন্নিবেশের পরিমার্জিত প্রত্যাশিত খরচের পাশাপাশি অপসারণের পরিমার্জিত প্রত্যাশিত খরচ হল O(1)।
অতিরিক্তভাবে, শীর্ষ-স্তরের টেবিলের চূড়ান্ত আকার বা যেকোনো সাব টেবিলের গতিশীল ক্ষেত্রে কোনো পূর্ব জ্ঞান নেই। টেবিলের প্রত্যাশিত O(m) স্থান বজায় রাখার একটি কৌশল হল পর্যাপ্ত সংখ্যক সন্নিবেশ এবং মুছে ফেলার অভিজ্ঞতা হলে একটি সম্পূর্ণ পুনর্নির্মাণের অনুরোধ করা। যতক্ষণ পর্যন্ত সন্নিবেশ বা মুছে ফেলার মোট সংখ্যা শেষ নির্মাণের সময় উপাদানের সংখ্যাকে ছাড়িয়ে যায়, ততক্ষণ সম্পূর্ণ রিহ্যাশিং বিবেচনা করে সন্নিবেশ এবং মুছে ফেলার পরিমার্জিত প্রত্যাশিত খরচ O(1) থেকে যায়।
