30. Hash Map / Hash Table
Hash Map বা Hash Table হলো হ্যাশিং টেকনিক ব্যবহার করে তৈরি একটি ডেটা স্ট্রাকচার যা মূলত Key-Value পেয়ার হিসেবে ডেটা স্টোর করে। এটি ইন্টারভিউ এবং রিয়েল-টাইম অ্যাপ্লিকেশনে সবচেয়ে বেশি ব্যবহৃত ডেটা স্ট্রাকচারগুলোর একটি।
1. Hash Map অপারেশনসমূহ
হ্যাশ ম্যাপে মূলত তিনটি কাজ সবচেয়ে বেশি হয়:
- Insert (put): নতুন Key এবং Value সেট করা।
- Search (get): নির্দিষ্ট Key দিয়ে Value খুঁজে বের করা।
- Delete (remove): নির্দিষ্ট Key এবং তার Value ডিলিট করা।
2. কলিশন রেজোলিউশন (Collision Resolution)
যখন দুটি ভিন্ন Key একই ইনডেক্স পায়, তখন তা সমাধানের জন্য নিচের টেকনিকগুলো ব্যবহার করা হয়:
A. Chaining (Separate Chaining)
এই পদ্ধতিতে প্রতিটি ইনডেক্সে একটি লিঙ্কড লিস্ট (Linked List) থাকে। যদি একাধিক Key একই ইনডেক্স পায়, তবে তারা ওই লিস্টের শেষে যুক্ত হয়।
- সুবিধা: টেবিল ফুল হয়ে গেলেও ডেটা ইনসার্ট করা যায়।
- অসুবিধা: লিস্ট বড় হয়ে গেলে সার্চিং স্লো হয়ে যায় ($O(n)$)।
B. Open Addressing
এখানে লিঙ্কড লিস্ট ব্যবহার না করে টেবিলের অন্য কোনো খালি স্লট খোঁজা হয়।
- Linear Probing: যদি স্লট পূর্ণ থাকে, তবে তার ঠিক পরের স্লটটি চেক করা হয় ($i+1, i+2...$)।
- Quadratic Probing: এখানে এক এক করে না খুঁজে গ্যাপ বাড়িয়ে খোঁজা হয় ($i+1^2, i+2^2...$) যাতে জোটবদ্ধতা বা Clustering না হয়।
- Double Hashing: যদি কলিশন হয়, তবে দ্বিতীয় আর একটি হ্যাশ ফাংশন ব্যবহার করে নতুন ইনডেক্স বের করা হয়।
3. রিহ্যাশিং (Rehashing)
যখন হ্যাশ টেবিলের ডেটা অনেক বেড়ে যায় এবং Load Factor (সাধারণত ০.৭৫) ছাড়িয়ে যায়, তখন টেবিলের পারফরম্যান্স ঠিক রাখতে এই পদ্ধতি ব্যবহার করা হয়।
🛠 কর্মপদ্ধতি (Step-by-Step Logic)
- বর্তমান টেবিলের সাইজ দ্বিগুণ করা হয়।
- নতুন সাইজ অনুযায়ী নতুন একটি হ্যাশ টেবিল তৈরি করা হয়।
- পুরনো টেবিলের প্রতিটি ডেটাকে পুনরায় হ্যাশ ফাংশন দিয়ে নতুন টেবিলে স্থানান্তর করা হয়।
📊 কমপ্লেক্সিটি অ্যানালাইসিস (General Complexity)
| Operation | Average Case | Worst Case |
|---|---|---|
| Insertion | O(1) | O(n) |
| Deletion | O(1) | O(n) |
| Search | O(1) | O(n) |
দ্রষ্টব্য: ভালো হ্যাশ ফাংশন এবং লোড ফ্যাক্টর মেইনটেইন করলে লিনিয়ার টাইম (O(1)) পাওয়া সম্ভব।
স্ট্যাক বনাম কিউ বনাম হ্যাশ ম্যাপ
- Stack/Queue: সিকোয়েন্সিয়াল ডেটা ম্যানেজমেন্টের জন্য।
- Hash Map: খুব দ্রুত ডেটা খোঁজ বা ম্যাপিংয়ের জন্য।
IMPORTANT
হ্যাশ ম্যাপে Worst Case Complexity $O(n)$ তখনই হয় যখন সব ডেটা কলিশনের কারণে একই ইনডেক্সে (চেইনিংয়ে) জমা হয়। আধুনিক ল্যাঙ্গুয়েজগুলো (যেমন জাভা ৮+) চেইনিংয়ে লিস্টের বদলে Self-balancing Tree ব্যবহার করে একে $O(\log n)$-এ নামিয়ে আনে।
TIP
রিহ্যাশিং একটি ব্যয়বহুল (Expensive) অপারেশন, তাই শুরুতে টেবিলের সাইজ এমনভাবে দেওয়া উচিত যাতে ঘনঘন রিহ্যাশিং না লাগে।