ডেটা স্ট্রাকচারে ওভারফ্লো হ্যান্ডলিং

একটি নতুন জোড়া (কী, উপাদান) পূর্ণ হওয়ার জন্য হোম বাকেটের সময় একটি ওভারফ্লো ঘটে।

আমরা

পূর্ণ নয় এমন একটি বালতির জন্য কিছু পদ্ধতিগতভাবে হ্যাশ টেবিল অনুসন্ধান করুন৷

• লিনিয়ার প্রোবিং (লিনিয়ার ওপেন অ্যাড্রেসিং)।
• চতুর্মুখী অনুসন্ধান।
• র্যান্ডম প্রোবিং।

প্রতিটি বালতিকে সমস্ত জোড়ার একটি তালিকা রাখার অনুমতি দিয়ে ওভারফ্লো দূর করুন যার জন্য এটি হোম বালতি৷

• অ্যারে লিনিয়ার তালিকা।
• চেইন।

সমস্ত উপাদান সরাসরি হ্যাশ টেবিলে সংরক্ষণ করা হয়েছে তা নিশ্চিত করার জন্য ওপেন অ্যাড্রেসিং সঞ্চালিত হয়, এইভাবে এটি বিভিন্ন পদ্ধতি প্রয়োগ করে সংঘর্ষের সমাধান করার চেষ্টা করে।

সারণীর পরবর্তী খোলা স্লটে ডেটা রেখে সংঘর্ষের সমাধান করতে লিনিয়ার প্রোবিং করা হয়।

লিনিয়ার প্রোবিং এর কর্মক্ষমতা

• সবচেয়ে খারাপ ক্ষেত্রে ফাইন্ড/ইনসার্ট/মুছে ফেলার সময় হল θ(m), যেখানে m কে টেবিলে জোড়ার সংখ্যা হিসাবে ধরা হয়।
• এটি ঘটে যখন সমস্ত জোড়া একই ক্লাস্টারে থাকে।

লিনিয়ার প্রোবিং এর সমস্যা

• শনাক্তকারীরা একসাথে ক্লাস্টার করার প্রবণতা করছে
• সংলগ্ন ক্লাস্টারগুলি একত্রিত হওয়ার প্রবণতা রয়েছে
• অনুসন্ধানের সময় বাড়ান বা বাড়ান

চতুর্মুখী অনুসন্ধান

লিনিয়ার প্রোবিং সার্চ বাকেট (H(x)+i2)%b; H(x) x

দ্বিঘাত প্রোবিং i-এর একটি দ্বিঘাত ফাংশনকে ইনক্রিমেন্ট হিসেবে প্রয়োগ করে

1<=i<=(b-1)/2

b কে 4j+3 ফর্মের একটি মৌলিক সংখ্যা হিসাবে নির্দেশ করা হয়, j হল একটি পূর্ণসংখ্যা

এলোমেলো অনুসন্ধান

র্যান্ডম প্রোবিং এলোমেলো সংখ্যার সাথে একত্রিত করে কাজ করে।

H(x):= (H’(x) + S[i]) % b
S[i] is a table along with size b-1
S[i] is indicated as a random permutation of integers [1, b-1].