ওভারফ্লো ঘটে যখন একটি নতুন জোড়া (key, element) এর জন্য হোম বাকেট পূর্ণ থাকে।
আমরা ওভারফ্লো নিম্নলিখিত উপায়গুলো দিয়ে সমাধান করতে পারি:
হ্যাশ টেবিলে সিস্টেমেটিকভাবে সার্চ করুন এমন একটি বাকেটের জন্য যা পূর্ণ নয়।
- লিনিয়ার প্রোবিং (লিনিয়ার ওপেন অ্যাড্রেসিং)।
- কোয়াড্রাটিক প্রোবিং।
- র্যান্ডম প্রোবিং।
প্রতিটি বাকেটকে তার হোম বাকেট হওয়া সকল জোড়ার একটি লিস্ট রাখতে দিয়ে ওভারফ্লো দূর করুন।
- অ্যারে লিনিয়ার লিস্ট।
- চেইন।
ওপেন অ্যাড্রেসিং করা হয় এটি নিশ্চিত করার জন্য যে সকল এলিমেন্ট সরাসরি হ্যাশ টেবিলে স্টোর হয়, সুতরাং এটি বিভিন্ন মেথড বাস্তবায়ন করে колиশন রেজলভ করার চেষ্টা করে।
লিনিয়ার প্রোবিং করা হয় колиশন রেজলভ করার জন্য ডেটাকে টেবিলের পরের খালি স্লটে রাখা।
লিনিয়ার প্রোবিং-এর পারফরম্যান্স
- ওয়ার্স্ট-কেস ফাইন্ড/ইনসার্ট/ইরেজ টাইম হলো θ(m), যেখানে m হলো টেবিলে থাকা জোড়ার সংখ্যা।
- এটি ঘটে যখন সকল জোড়া একই ক্লাস্টারে থাকে।
লিনিয়ার প্রোবিং-এর সমস্যা
- আইডেন্টিফায়াররা একসাথে ক্লাস্টার হওয়ার প্রবণতা রাখে
- সন্নিহিত ক্লাস্টাররা একত্রিত হওয়ার প্রবণতা রাখে
- সার্চ টাইম বাড়ায় বা বর্ধন করে
কোয়াড্রাটিক প্রোবিং
লিনিয়ার প্রোবিং বাকেটগুলো সার্চ করে (H(x)+i2)%b; H(x) বোঝায় x-এর হ্যাশ ফাংশন।
কোয়াড্রাটিক প্রোবিং i-র একটি কোয়াড্রাটিক ফাংশন বাস্তবায়ন করে ইনক্রিমেন্ট হিসেবে।
বাকেটগুলো পরীক্ষা করুন H(x), (H(x)+i2)%b, (H(x)-i2)%b, 1<=i<=(b-1)/2 এর জন্য।
b নির্দেশ করা হয় 4j+3 ফর্মের একটি প্রাইম নম্বর হিসেবে, j হলো একটি ইন্টিজার।
র্যান্ডম প্রোবিং
র্যান্ডম প্রোবিং র্যান্ডম নাম্বার সহ বাস্তবায়ন করা হয়।
H(x):= (H’(x) + S[i]) % b S[i] হলো সাইজ b-1-এর একটি টেবিল S[i] নির্দেশ করা হয় ইন্টিজার [1, b-1]-এর একটি র্যান্ডম পারমুটেশন হিসেবে।
