हैश टेबल एक डेटा संरचना है जिसका उपयोग की-वैल्यू पेयर को स्टोर करने के लिए किया जाता है। हैश फ़ंक्शन का उपयोग हैश तालिका द्वारा किसी इंडेक्स को एक सरणी में गणना करने के लिए किया जाता है जिसमें एक तत्व डाला या खोजा जाएगा।
यह डबल लिंक्ड सूचियों के साथ हैश टेबल्स को लागू करने के लिए एक 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