হ্যাশিং হল একটি পদ্ধতি যার মাধ্যমে আমরা যেকোন দৈর্ঘ্যের ডেটা উপাদানকে একটি নির্দিষ্ট আকারের কীতে ম্যাপ করতে পারি। হ্যাশিং কী-মান জোড়া হিসাবে কাজ করে।
হ্যাশিং ফাংশন হল সেই ফাংশন যা হ্যাশ ম্যাপে ম্যাপিং করে। হ্যাশ ফাংশনে ইনপুট হিসাবে দেওয়া ডেটা উপাদানগুলি একই হ্যাশ কী পেতে পারে। এই ক্ষেত্রে উপাদানগুলি ওভারল্যাপ হতে পারে। একই হ্যাশ কী আছে এমন উপাদানগুলির ওভারল্যাপিং এড়াতে চেইনিংয়ের ধারণাটি চালু করা হয়েছিল।
একটি হ্যাশম্যাপ তৈরি করা হচ্ছে
একটি হ্যাশম্যাপ তৈরি করার জন্য আমাদের হ্যাশিং ফাংশন প্রয়োজন যা ডেটা উপাদানের সূচকের মান নির্ধারণ করবে।
আমরা এন buckets সঙ্গে একটি হ্যাশ টেবিল আছে. একটি হ্যাশ টেবিলে একটি নোড সন্নিবেশ করান , আমাদেরকে একটি হ্যাশ ফাংশন দেওয়া হয়
হিসেবেhashIndex =কী % noOfBuckets
এখন, আমরা এই হ্যাশ ফাংশনটি ব্যবহার করব এবং হ্যাশম্যাপ-এ প্রতিটি সন্নিবেশিত মানের হ্যাশন্ডেক্স গণনা করব। .
-
উপাদান সন্নিবেশ করুন এবং প্রদত্ত কী মানের হ্যাশইন্ডেক্স গণনা করুন এবং তারপর তালিকার শেষে নতুন নোড সন্নিবেশ করুন৷
-
একটি নোড মুছে ফেলার জন্য, আমরা হ্যাশ সূচকটি গণনা করব এবং হ্যাশ সূচকের সাথে সম্পর্কিত বালতিতে আমরা বালতির উপাদানটি অনুসন্ধান করব এবং এটি সরিয়ে ফেলব৷
উদাহরণ
#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
