সংজ্ঞা
ডাইনামিক পারফেক্ট হ্যাশিং হলো একটি প্রোগ্রামিং পদ্ধতি যা হ্যাশ টেবিল ডেটা স্ট্রাকচারে колиশন সমাধানের জন্য ব্যবহৃত হয়।
অ্যাপ্লিকেশন
অন্য হ্যাশ টেবিল পদ্ধতির চেয়ে বেশি মেমরি ব্যবহার করলেও, এই পদ্ধতি বড় ডেটা সেটে দ্রুত কোয়ারি, ইনসার্শন এবং ডিলিশন করার জন্য আদর্শ।
অনুপ্রবেশ
ডাইটজফেলবিংয়ার ও তার সহকর্মীরা একটি ডাইনামিক ডিকশনারি অ্যালগরিদম ব্যাখ্যা করেছেন যা, যখন m সংখ্যক আইটেম ক্রমাগত ডিকশনারিতে যুক্ত করা হয়, সদস্য কোয়ারি সর্বদা কনস্ট্যান্ট টাইম বা O(1) ওয়ার্স্ট-কেস টাইমে সম্পন্ন হয়, মোট স্টোরেজ O(m) (লিনিয়ার), এবং O(1) এক্সপেক্টেড অ্যামোর্টাইজড ইনসার্শন এবং ডিলিশন টাইম (অ্যামোর্টাইজড কনস্ট্যান্ট টাইম)। ডাইনামিক কেসে, যখন একটি কী হ্যাশ টেবিলে ইনসার্ট করা হয়, যদি তার এন্ট্রি তার নিজস্ব সাব-টেবিলে দখল করা থাকে, তবে একটি колиশন ঘটে এবং সাব-টেবিলটি তার নতুন মোট এন্ট্রি কাউন্ট এবং র্যান্ডমলি নির্বাচিত হ্যাশ ফাংশন অনুযায়ী পুনর্গঠিত হয়। যেহেতু সেকেন্ড-লেভেল টেবিলের লোড ফ্যাক্টর কম রাখা হয়, পুনর্গঠন কম ঘটে, এবং ইনসার্শন ও ডিলিশনের অ্যামোর্টাইজড এক্সপেক্টেড কস্ট O(1) হয়।
অতিরিক্তভাবে, ডাইনামিক কেসে টপ-লেভেল টেবিল বা যেকোনো সাব-টেবিলের চূড়ান্ত আকারের কোনো পূর্বজ্ঞান থাকে না। টেবিলের প্রত্যাশিত O(m) স্পেস বজায় রাখার একটি কৌশল হলো যথেষ্ট সংখ্যক ইনসার্শন এবং ডিলিশন হলে পূর্ণ পুনর্গঠন শুরু করা। যতক্ষণ না মোট ইনসার্শন বা ডিলিশন সংখ্যা শেষ নির্মাণের সময় উপস্থিত এলিমেন্টের সংখ্যা অতিক্রম করে, পূর্ণ রি-হ্যাশিং বিবেচনা করলে ইনসার্শন এবং ডিলিশনের অ্যামোর্টাইজড এক্সপেক্টেড কস্ট O(1) থাকে।
