হ্যাশিং হলো যে মেথড দ্বারা আমরা যেকোনো লেন্থের ডেটা এলিমেন্টকে একটি ফিক্সড সাইজ কি-এ ম্যাপ করতে পারি। হ্যাশিং কি-ভ্যালু পেয়ার হিসেবে কাজ করে।
হ্যাশিং ফাংশন হলো वह ফাংশন যা হ্যাশ ম্যাপে ম্যাপিং করে। হ্যাশ ফাংশনে ইনপুট হিসেবে দেওয়া ডেটা এলিমেন্টগুলো একই হ্যাশ কি পেতে পারে। এই ক্ষেত্রে এলিমেন্টগুলো ওভারল্যাপ করতে পারে। একই হ্যাশ কি 가진 এলিমেন্টগুলোর ওভারল্যাপ এড়াতে চেইনিং কনসেপ্ট চালু করা হয়েছিল।
হ্যাশম্যাপ তৈরি করা
হ্যাশম্যাপ তৈরি করতে হলে হ্যাশিং ফাংশন দরকার যা ডেটা এলিমেন্টের ইনডেক্স ভ্যালু ডিফাইন করবে।
আমাদের একটি হ্যাশ টেবিল আছে, n বালতির সাথে। একটি নোড হ্যাশ টেবিল-এ ইনসার্ট করতে হলে, আমাদের একটি হ্যাশ ফাংশন দেওয়া থাকে যেমন
hashIndex = key % noOfBuckets
এখন, আমরা এই হ্যাশ ফাংশন ব্যবহার করে হ্যাশম্যাপ-এ ইনসার্ট হওয়া প্রতিটি ভ্যালুর hashIndex ক্যালকুলেট করব।
এলিমেন্ট ইনসার্ট করুন এবং দেওয়া কি ভ্যালুর hashIndex ক্যালকুলেট করুন এবং তারপর নতুন নোডটিকে লিস্টের শেষে ইনসার্ট করুন।
একটি নোড ডিলিট করতে, আমরা হ্যাশ ইনডেক্স ক্যালকুলেট করব এবং হ্যাশ ইনডেক্সের সাথে সম্পর্কিত বালতিতে এলিমেন্টটি সার্চ করে রিমুভ করব।
উদাহরণ
#include<iostream> #include <list> using namespace std; class Hash{ int BUCKET; list < int >*table; public: Hash (int V); void insertItem (int x); void deleteItem (int key); int hashFunction (int x){ return (x % BUCKET); } void displayHash (); }; Hash::Hash (int b){ this->BUCKET = b; table = new list < int >[BUCKET]; } void Hash::insertItem (int key){ int index = hashFunction (key); table[index].push_back (key); } void Hash::deleteItem (int key){ int index = hashFunction (key); list < int >::iterator i; for (i = table[index].begin (); i != table[index].end (); i++){ if (*i == key) break; } if (i != table[index].end ()) table[index].erase (i); } void Hash::displayHash (){ for (int i = 0; i < BUCKET; i++){ cout << i; for (auto x:table[i]) cout << " --> " << x; cout << endl; } } int main (){ int a[] = { 5, 12, 67, 9, 16 }; int n = 5; Hash h (7); for (int i = 0; i < n; i++) h.insertItem (a[i]); h.deleteItem (12); h.displayHash (); return 0; }
আউটপুট
0 1 2 --> 9 --> 16 3 4 --> 67 5 --> 5 6
