হ্যাশ টেবিল হলো একটি ডেটা স্ট্রাকচার যা কি-ভ্যালু পেয়ার স্টোর করতে ব্যবহৃত হয়। হ্যাশ ফাংশন হ্যাশ টেবিলে ব্যবহার হয় একটি অ্যারের মধ্যে ইনডেক্স কম্পিউট করতে যেখানে এলিমেন্ট ইনসার্ট বা সার্চ হবে।
লিনিয়ার প্রোবিং ওপেন অ্যাড্রেসড হ্যাশ টেবিলে একটি কলিশন রেজোলভিং টেকনিক। এই মেথডে, হ্যাশ টেবিলের প্রতিটি সেল একটি একক কি-ভ্যালু পেয়ার স্টোর করে। যদি একটি নতুন কি ম্যাপ করে হ্যাশ টেবিলের একটি সেলে যা ইতিমধ্যে অন্য কি দিয়ে অকুপায়ড থাকে, তবে কলিশন হয়। এই মেথড টেবিলে সবচেয়ে নিকটবর্তী ফ্রি লোকেশন সার্চ করে এবং নতুন কি সেখানে ইনসার্ট করে।
এটি লিনিয়ার প্রোবিং সহ হ্যাশ টেবিল ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম।
অ্যালগরিদম
শুরু
Insert(int k, int v) ফাংশন ডিক্লেয়ার করো
hash_val, init, delindex ইন্টিজার পয়েন্টার হিসেবে ডিক্লেয়ার করো।
hash_val = HashFunc(k) ইনিশিয়ালাইজ করো
init = -1 ইনিশিয়ালাইজ করো
delindex = -1 ইনিশিয়ালাইজ করো
while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k != k))
if (init == -1)
init = hash_val
if (ht[hash_val] == DelNode::getNode())
delindex = hash_val
hash_val = HashFunc(hash_val + 1)
if (ht[hash_val] == NULL or hash_val == init)
if (delindex != -1)
ht[delindex] = new HashTable(k, v)
else
ht[hash_val] = new HashTable(k, v)
if (init != hash_val)
if (ht[hash_val] != DelNode::getNode())
if (ht[hash_val] != NULL)
if (ht[hash_val]->k == k)
ht[hash_val]->v = v
else
ht[hash_val] = new HashTable(k, v)
শেষ।
কি ভ্যালু সার্চ করার জন্য:
শুরু
SearchKey(int k) ফাংশন ডিক্লেয়ার করো
hash_val, init ইন্টিজার ডেটা টাইপ হিসেবে ডিক্লেয়ার করো।
hash_val = HashFunc(k) ইনিশিয়ালাইজ করো
init = -1 ইনিশিয়ালাইজ করো
while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k != k)
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (ht[hash_val] == NULL or hash_val == init)
return -1
else
return ht[hash_val]->v
শেষ।
ডিলিট করার জন্য:
শুরু
Remove(int k) ফাংশন ডিক্লেয়ার করো
hash_val, init ইন্টিজার ডেটা টাইপ হিসেবে ডিক্লেয়ার করো।
hash_val = HashFunc(k) ইনিশিয়ালাইজ করো
init = -1 ইনিশিয়ালাইজ করো
while (hash_val != init and (ht[hash_val] == DelNode::getNode() or ht[hash_val] != NULL and ht[hash_val]->k != k))
if (init == -1)
init = hash_val
hash_val = HashFunc(hash_val + 1)
if (hash_val != init and ht[hash_val] != NULL)
delete ht[hash_val]
ht[hash_val] = DelNode::getNode()
শেষ।
উদাহরণ কোড
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int T_S = 5;
class HashTable {
public:
int k;
int v;
HashTable(int k, int v) {
this->k = k;
this->v = v;
}
};
class DelNode: public HashTable {
private:
static DelNode *en;
DelNode(): HashTable(-1, -1) {}
public:
static DelNode *getNode() {
if (en == NULL)
en = new DelNode();
return en;
}
};
DelNode *DelNode::en = NULL;
class HashMapTable {
private:
HashTable **ht;
public:
HashMapTable() {
ht = new HashTable* [T_S];
for (int i = 0; i < T_S; i++) {
ht[i] = NULL;
}
}
int HashFunc(int k) {
return k % T_S;
}
void Insert(int k, int v) {
int hash_val = HashFunc(k);
int init = -1;
int delindex = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
if (init == -1)
init = hash_val;
if (ht[hash_val] == DelNode::getNode())
delindex = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init) {
if (delindex != -1)
ht[delindex] = new HashTable(k, v);
else
ht[hash_val] = new HashTable(k, v);
}
if (init != hash_val) {
if (ht[hash_val] != DelNode::getNode()) {
if (ht[hash_val] != NULL) {
if (ht[hash_val]->k == k)
ht[hash_val]->v = v;
}
} else
ht[hash_val] = new HashTable(k, v);
}
}
int SearchKey(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (ht[hash_val] == NULL || hash_val == init)
return -1;
else
return ht[hash_val]->v;
}
void Remove(int k) {
int hash_val = HashFunc(k);
int init = -1;
while (hash_val != init && (ht[hash_val] == DelNode::getNode() || ht[hash_val] != NULL && ht[hash_val]->k != k)) {
if (init == -1)
init = hash_val;
hash_val = HashFunc(hash_val + 1);
}
if (hash_val != init && ht[hash_val] != NULL) {
delete ht[hash_val];
ht[hash_val] = DelNode::getNode();
}
}
~HashMapTable() {
delete[] ht;
}
};
int main() {
HashMapTable hash;
int k, v;
int c;
while (1) {
cout << "1. Insert element into the table" << endl;
cout << "2. Search element from the key" << endl;
cout << "3. Delete element at a key" << endl;
cout << "4. Exit" << endl;
cout << "Enter your choice: ";
cin >> c;
switch (c) {
case 1:
cout << "Enter element to be inserted: ";
cin >> v;
cout << "Enter key at which element to be inserted: ";
cin >> k;
hash.Insert(k, v);
break;
case 2:
cout << "Enter key of the element to be searched: ";
cin >> k;
if (hash.SearchKey(k) == -1) {
cout << "No element found at key " << k << endl;
continue;
} else {
cout << "Element at key " << k << " : ";
cout << hash.SearchKey(k) << endl;
}
break;
case 3:
cout << "Enter key of the element to be deleted: ";
cin >> k;
hash.Remove(k);
break;
case 4:
exit(1);
default:
cout << "\nEnter correct option\n";
}
}
return 0;
}আউটপুট
1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 1 Enter element to be inserted: 10 Enter key at which element to be inserted: 2 ... (মেনু চালু থাকে, ইনসার্ট, সার্চ, ডিলিট অপারেশন দেখানো হয়েছে) ... Enter your choice: 4
