सी ++ प्रोग्राम डबल हैशिंग के साथ हैश टेबल्स को लागू करने के लिए

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

डबल हैशिंग ओपन एड्रेसेड हैश टेबल में एक टकराव समाधान तकनीक है। डबल हैशिंग टकराव होने पर दूसरे हैश फ़ंक्शन को कुंजी के लिए उपयोग करने के विचार का उपयोग करता है।

यह डबल हैशिंग के साथ हैश टेबल्स को लागू करने के लिए एक C++ प्रोग्राम है।

एल्गोरिदम

खोज के लिए एक कुंजी:

Begin
   Declare Function SearchKey(int k, HashTable *ht)
      int hashVal= HashFunc1(k, ht->s)
      int stepSize= HashFunc2(k, ht->s)
      while (ht->t[hashVal].info != Emp and
         ht->t[hashVal].e != k)
            hashVal = hashVal + stepSize
            hashVal = hashVal % ht->s
      return hashVal
End

सम्मिलित करने के लिए:

Begin.
   Declare Function Insert(int k, HashTable *ht)
      int pos = SearchKey(k, ht)
      if (ht->t[pos].info != Legi )
         ht->t[pos].info = Legi
         ht->t[pos].e = k
End

प्रदर्शन के लिए:

Begin
   Declare function display(HashTable *ht)
      for (int i = 0; i < ht->s; i++)
         int v= ht->t[i].e;
         if (!v)
            Print "Position: "
               Print the position of the pointer
            Print " Element: Null"
         else
            Print "Position: "
               Print the position of the pointer
            Print " Element: "
               Print the element
End.

रीहैश फ़ंक्शन के लिए:

Begin
   Declare function Rehash(HashTable *ht)
      int s = ht->s
      HashTableEntry *t= ht->t
      ht = initiateTable(2*s)
      for (int i = 0; i < s; i++)
         if (t[i].info == Legi)
            Insert(t[i].e, ht)
      free(t)
      return ht
End.

उदाहरण कोड

#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;
enum EntryType {Legi, Emp};
struct HashTableEntry {
   int e;
   enum EntryType info;
};
struct HashTable {
   int s;
   HashTableEntry *t;
};
int HashFunc1(int k, int s) {
   return k % s;
}
int HashFunc2(int k, int s) {
   return (k * s - 1) % s;
}
HashTable *initiateTable(int s) {
   HashTable *ht;
   if (s < T_S) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   ht= new HashTable;
   if (ht == NULL) {
      cout<<"Out of Space"<<endl;
      return NULL;
   }
   ht->s = s;
   ht->t = new HashTableEntry[ht->s];
   if (ht->t== NULL) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   for (int i = 0; i < ht->s; i++) {
      ht->t[i].info = Emp;
      ht->t[i].e=NULL;
   }
   return ht;
}
int SearchKey(int k, HashTable *ht) {
   int hashVal= HashFunc1(k, ht->s);
   int stepSize= HashFunc2(k, ht->s);
   while (ht->t[hashVal].info != Emp &&
      ht->t[hashVal].e != k) {
         hashVal = hashVal + stepSize;
         hashVal = hashVal % ht->s;
      }
      return hashVal;
}
void Insert(int k, HashTable *ht) {
   int pos = SearchKey(k, ht);
   if (ht->t[pos].info != Legi ) {
      ht->t[pos].info = Legi;
      ht->t[pos].e = k;
   }
}
void display(HashTable *ht) {
   for (int i = 0; i < ht->s; i++) {
      int v= ht->t[i].e;
      if (!v)
         cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
      else
         cout<<"Position: "<<i + 1<<" Element: "<<v<<endl;
   }
}
HashTable *Rehash(HashTable *ht) {
   int s = ht->s;
   HashTableEntry *t= ht->t;
   ht = initiateTable(2*s);
   for (int i = 0; i < s; i++) {
      if (t[i].info == Legi)
         Insert(t[i].e, ht);
   }
   free(t);
   return ht;
}
int main() {
   int v, s, pos, i = 1;
   int c;
   HashTable *ht;
   while(1) {
      cout<<"1.Initialize size of the table"<<endl;
      cout<<"2.Insert element into the table"<<endl;
      cout<<"3.Display Hash Table"<<endl;
      cout<<"4.Rehash Hash Table"<<endl;
      cout<<"5.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter size of the Hash Table: ";
            cin>>s;
            ht = initiateTable(s);
         break;
         case 2:
            if (i > ht->s) {
               cout<<"Table is Full, Rehash the table"<<endl;
               continue;
            }
            cout<<"Enter element to be inserted: ";
            cin>>v;
            Insert(v, ht);
            i++;
         break;
         case 3:
            display(ht);
         break;
         case 4:
            ht= Rehash(ht);
         break;
         case 5:
            exit(1);
         default:
         cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}

आउटपुट

1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 1
Enter size of the Hash Table: 4
Table Size is Too Small
Enter your choice: 1
Enter size of the Hash Table: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 1
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 3
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 5
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 6
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 7
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 8
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice:
9
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 10
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 11
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 12
Enter correct option
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Table is Full, Rehash the table
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 10
Position: 2 Element: 1
Position: 3 Element: 11
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 4
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: Null
Position: 2 Element: 1
Position: 3 Element: Null
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 2
Enter element to be inserted: 20
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 3
Position: 1 Element: 20
Position: 2 Element: 1
Position: 3 Element: Null
Position: 4 Element: 3
Position: 5 Element: 4
Position: 6 Element: 5
Position: 7 Element: 6
Position: 8 Element: 7
Position: 9 Element: 8
Position: 10 Element: 9
Position: 11 Element: 10
Position: 12 Element: 11
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: Null
Position: 18 Element: Null
Position: 19 Element: Null
Position: 20 Element: Null
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash Hash Table
5.Exit
Enter your choice: 5