একটি হ্যাশ টেবিল হল একটি ডেটা স্ট্রাকচার যা কী-মান জোড়া সংরক্ষণ করতে ব্যবহৃত হয়। হ্যাশ ফাংশন হ্যাশ টেবিল দ্বারা একটি অ্যারেতে একটি সূচক গণনা করতে ব্যবহৃত হয় যেখানে একটি উপাদান সন্নিবেশ করা হবে বা অনুসন্ধান করা হবে৷
এটি দ্বিগুণ লিঙ্কযুক্ত তালিকার সাথে হ্যাশ টেবিল চেইনিং বাস্তবায়নের জন্য একটি C++ প্রোগ্রাম।
অ্যালগরিদম
ঢোকানোর জন্য:
Begin Declare Function insert(int k, int v) int hash_v= HashFunc(k) HashTableEntry *en = ht[hash_v] if (en == NULL) en = new HashTableEntry en->d = v en->k = k en->n = NULL en->p = NULL ht[hash_v] = en top[hash_v] = en else while (en != NULL) en = en->n en = new HashTableEntry en->d = v en->k = k en->n = NULL en->p = top[hash_v] top[hash_v]->n = en top[hash_v] = en End
মোছার জন্য:
Begin Declare function remove(int k) int hash_v = HashFunc(k) HashTableEntry *en = ht[hash_v] if (en->k != k || en == NULL) Print No Element found at key return while (en != NULL) if (en->n == NULL) if (en->p == NULL) ht[hash_v] = NULL top[hash_v] = NULL delete en break else top[hash_v] = en->p top[hash_v]->n = NULL delete en en = top[hash_v] en = en->n End
একটি মূল মান অনুসন্ধানের জন্য:
Begin Declare function SearchKey(int k) int hash_v = HashFunc(k) bool flag = false HashTableEntry* en = ht[hash_v] if (en != NULL) while (en != NULL) if (en->k == k) flag = true if (flag) Print Element found at key print en->d en = en->n if (!flag) Print “No Element found at key.” End.
উদাহরণ কোড
#include <iostream>
const int T_S = 200;
using namespace std;
struct HashTableEntry {
int d, k;
HashTableEntry *n;
HashTableEntry *p;
};
class HashMapTable {
public:
HashTableEntry **ht, **top;
HashMapTable() {
ht = new HashTableEntry*[T_S];
top = new HashTableEntry*[T_S];
for (int i = 0; i < T_S; i++) {
ht[i] = NULL;
top[i] = NULL;
}
}
int HashFunc(int key) {
return key % T_S;
}
void insert(int k, int v) {
int hash_v= HashFunc(k);
HashTableEntry *en = ht[hash_v];
if (en == NULL) {
en = new HashTableEntry;
en->d = v;
en->k = k;
en->n = NULL;
en->p = NULL;
ht[hash_v] = en;
top[hash_v] = en;
} else {
while (en != NULL)
en = en->n;
en = new HashTableEntry;
en->d = v;
en->k = k;
en->n = NULL;
en->p = top[hash_v];
top[hash_v]->n = en;
top[hash_v] = en;
}
}
void remove(int k) {
int hash_v = HashFunc(k);
HashTableEntry *en = ht[hash_v];
if (en->k != k || en == NULL) {
cout<<"No Element found at key: "<<k<<endl;
return;
}
while (en != NULL) {
if (en->n == NULL) {
if (en->p == NULL) {
ht[hash_v] = NULL;
top[hash_v] = NULL;
delete en;
break;
} else {
top[hash_v] = en->p;
top[hash_v]->n = NULL;
delete en;
en = top[hash_v];
}
}
en = en->n;
}
}
void SearchKey(int k) {
int hash_v = HashFunc(k);
bool flag = false;
HashTableEntry* en = ht[hash_v];
if (en != NULL) {
while (en != NULL) {
if (en->k == k) {
flag = true;
}
if (flag) {
cout<<"Element found at key "<<k<<": ";
cout<<en->d<<endl;
}
en = en->n;
}
}
if (!flag)
cout<<"No Element found at key "<<k<<endl;
}
~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;
hash.SearchKey(k);
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: 1 Enter key at which element to be inserted: 1 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: 2 Enter key at which element to be inserted: 3 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: 7 Enter key at which element to be inserted: 6 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: 4 Enter key at which element to be inserted: 5 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 2 Enter key of the element to be searched: 6 Element found at key 6: 7 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 3 Enter key of the element to be deleted: 1 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4
