हैश टेबल एक डेटा संरचना है जिसका उपयोग कुंजी-मूल्य जोड़े को संग्रहीत करने के लिए किया जाता है। हैश फ़ंक्शन का उपयोग हैश टेबल द्वारा एक सरणी में एक इंडेक्स की गणना करने के लिए किया जाता है जिसमें एक तत्व डाला या खोजा जाएगा।
लीनियर प्रोबिंग ओपन एड्रेस्ड हैश टेबल्स में टकराव समाधान की एक तकनीक है। इस विधि में, हैश टेबल का प्रत्येक सेल एक कुंजी-मूल्य जोड़ी संग्रहीत करता है। यदि एक नई कुंजी को हैश टेबल के उस सेल पर मैप करके टकराव होता है जो पहले से ही किसी अन्य कुंजी द्वारा कब्जा किया गया है। यह विधि टेबल में निकटतम मुक्त स्थान की खोज करती है और नई कुंजी को वहां डालती है।
यह लीनियर प्रोबिंग के साथ हैश टेबल्स को लागू करने के लिए एक C++ प्रोग्राम है।
एल्गोरिथम
सम्मिलन के लिए:
Begin Declare Function Insert(int k, int v) int hash_val = HashFunc(k) intialize init = -1 intialize 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 || 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) End.
कुंजी खोजने के लिए:
Begin Declare Function SearchKey(int k) int hash_val = HashFunc(k) int 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 End.
हटाने के लिए:
Begin Declare Function Remove(int k) int hash_val = HashFunc(k) intialize 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 && ht[hash_val] != NULL) delete ht[hash_val] ht[hash_val] = DelNode::getNode() End
उदाहरण कोड
#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 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: 1 Enter element to be inserted: 12 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: 15 Enter correct option 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: 15 Enter key at which element to be inserted: 8 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 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: 2 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: 2 No element found at key 2 1.Insert element into the table 2.Search element from the key 3.Delete element at a key 4.Exit Enter your choice: 4
