हैशिंग वह विधि है जिसके द्वारा हम किसी भी लम्बाई के डेटा तत्व को एक निश्चित आकार की कुंजी में मैप कर सकते हैं। हैशिंग की-वैल्यू पेयर के रूप में काम करता है।
हैशिंग फंक्शन वह फंक्शन है जो हैश मैप में मैपिंग करता है। हैश फ़ंक्शन में इनपुट के रूप में दिए गए डेटा तत्वों को समान हैश कुंजी मिल सकती है। इस मामले में, तत्व ओवरलैप हो सकते हैं। समान हैश कुंजी वाले तत्वों के ओवरलैपिंग से बचने के लिए चेनिंग की अवधारणा पेश की गई थी।
हैशमैप बनाना
हैशमैप बनाने के लिए हमें हैशिंग फ़ंक्शन की आवश्यकता होती है जो डेटा तत्व के सूचकांक मूल्य को परिभाषित करेगा।
हमारे पास एक हैश टेबल है, जिसमें n बकेट हैं। हैश तालिका . में नोड डालने के लिए , हमें एक हैश फ़ंक्शन दिया जाता है
हैशइंडेक्स =कुंजी% 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