29. Hashing - Introduction
Hashing হলো একটি অত্যন্ত শক্তিশালী টেকনিক যার মাধ্যমে খুব বিশাল পরিমাণ ডেটাকে একটি নির্দিষ্ট সাইজের টেবিলে এমনভাবে সাজানো হয় যাতে খুব দ্রুত (প্রায় O(1) সময়ে) ডেটা খুঁজে পাওয়া যায়।
1. Hashing কি? (Key to Index Mapping)
হ্যাশিং মূলত একটি Key কে একটি Index-এ রূপান্তর করার প্রক্রিয়া। এটি একটি ম্যাথমেটিক্যাল ফাংশন ব্যবহার করে কাজ করে, যাকে Hash Function বলা হয়।
উদাহরণস্বরূপ, আপনার কাছে অনেকগুলো নাম আছে এবং আপনি সেগুলো একটি ১০ সাইজের ঘরে রাখতে চান। হ্যাশ ফাংশন প্রতিটি নামকে ০ থেকে ৯ এর মধ্যে একটি নাম্বার দেবে, যা হবে ওই নামের ইনডেক্স।
2. হ্যাশ ফাংশন (Hash Function)
একটি ভালো হ্যাশ ফাংশনের বৈশিষ্ট্য হলো এটি একই ইনপুট দিলে সবসময় একই আউটপুট দেবে এবং ডেটাকে টেবিলের সব জায়গায় সমানভাবে ছড়িয়ে দেবে।
পপুলার মেথড:
- Division Method: $h(k) = k \pmod m$ (সবচেয়ে সহজ পদ্ধতি)।
- Multiplication Method: এখানে একটি কনস্ট্যান্ট ব্যবহার করে ইনডেক্স বের করা হয়।
- Mid-Square Method: কি এর বর্গ করে মাঝের অংশ নেওয়া হয়।
3. হ্যাশ টেবিল (Hash Table)
হ্যাশ টেবিল হলো একটি অ্যারে যেখানে হ্যাশ ফাংশন থেকে প্রাপ্ত ইনডেক্স অনুযায়ী ডেটা স্টোর করা হয়। প্রতিটি ইনডেক্সকে বলা হয় Bucket বা Slot।
4. ডিরেক্ট অ্যাড্রেসিং (Direct Addressing)
যদি আমাদের কাছে কি (Key) হিসেবে ছোট ইনটিজার থাকে, তবে আমরা কোনো হ্যাশ ফাংশন ছাড়াই সরাসরি ইনডেক্স হিসেবে কি ব্যবহার করতে পারি।
- সুবিধা: অনেক ফাস্ট (O(1))।
- অসুবিধা: যদি ভ্যালু রেঞ্জ অনেক বড় হয় (যেমন ১ থেকে ১ বিলিয়ন), তবে মেমরি অপচয় হয়।
5. কলিশন হ্যান্ডলিং (Collision Handling Intro)
যখন দুটি ভিন্ন কি (Key) হ্যাশ ফাংশনের মাধ্যমে একই ইনডেক্স পায়, তখন তাকে Collision বলা হয়। এটি সমাধানের প্রধান দুটি পদ্ধতি হলো:
- Chaining: একই ইনডেক্সে একটি লিঙ্কড লিস্ট (Linked List) তৈরি করা।
- Open Addressing: যদি কোনো ইনডেক্স ব্লক হয়, তবে অন্য খালি ইনডেক্স খুঁজে বের করা (Linear Probing, Quadratic Probing)।
6. লোড ফ্যাক্টর (Load Factor)
লোড ফ্যাক্টর ($\alpha$) হলো হ্যাশ টেবিলের মেমরি ব্যবহারের পরিমাপক। $$\alpha = \frac{\text{Total elements (n)}}{\text{Size of table (m)}}$$ যদি লোড ফ্যাক্টর ০.৭ বা তার বেশি হয়ে যায়, তবে টেবিলের সাইজ বাড়ানো (Rehashing) প্রইয়োজন হয়।
7. হ্যাশিংয়ের ব্যবহার (Applications)
- Dictionaries/Maps: আইটেম স্টোর এবং দ্রুত সার্চ করতে।
- Cache Management: ডেটা অস্থায়ীভাবে জমানোর জন্য।
- Database Indexing: টেবিলে ডেটা খোঁজার গতি বাড়াতে।
- Cryptography: পাসওয়ার্ড সিকিউরলি স্টোর করতে (SHA-256, MD5)।
📊 কমপ্লেক্সিটি অ্যানালাইসিস (General Complexity)
| Operation | Average Case | Worst Case |
|---|---|---|
| Search | O(1) | O(n) |
| Insert | O(1) | O(n) |
| Delete | O(1) | O(n) |
IMPORTANT
হ্যাশিংয়ের সবচেয়ে বড় শক্তি হলো এর Average Case Time Complexity, যা প্রায় সবসময় O(1)।
TIP
হ্যাশ টেবিল চুজ করার সময় এর Load Factor এবং Collision Resolution মেথডের ওপর নজর রাখা জরুরি।