हैश टेबल एक डेटा संरचना है जिसका उपयोग की-वैल्यू पेयर को स्टोर करने के लिए किया जाता है। हैश फ़ंक्शन का उपयोग हैश तालिका द्वारा एक अनुक्रमणिका को एक सरणी में गणना करने के लिए किया जाता है जिसमें एक तत्व डाला या खोजा जाएगा। द्विघात जांच ओपन एड्रेसेड हैश टेबल में एक टक्कर समाधान तकनीक है। यह मूल हैश इंडेक्स लेकर और एक खुले स्लॉट मिलने तक एक मनमानी द्विघात बहुपद के क्रमिक मूल्यों को जोड़कर संचालित होता है।
द्विघात जांच के साथ हैश टेबल्स को लागू करने के लिए यह एक C++ प्रोग्राम है।
एल्गोरिदम
खोज के लिए एक महत्वपूर्ण मान:
Begin Declare function SearchKey(int k, HashTable *ht) int pos = HashFunc(k, ht->s) intialize collisions = 0 while (ht->t[pos].info != Emp and ht->t[pos].e != k) pos = pos + 2 * ++collisions -1 if (pos >= ht->s) pos = pos - ht->s return pos 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 value = ht->t[i].e if (!value) print"Position: " print the current position Print" Element: Null" else print"Position: " print the current position 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. Source Code:
उदाहरण कोड
#include <iostream>
#include <cstdlib>
#define T_S 10
using namespace std;
enum EntryType {
Legi, Emp, Del};
struct HashTableEntry {
int e;
enum EntryType info;
};
struct HashTable {
int s;
HashTableEntry *t;
};
bool isPrime (int n) {
if (n == 2 || n == 3)
return true;
if (n == 1 || n % 2 == 0)
return false;
for (int i = 3; i * i <= n; i += 2)
if (n % i == 0)
return false;
return true;
}
int nextPrime(int n) {
if (n <= 0)
n == 3;
if (n % 2 == 0)
n++;
for (; !isPrime( n ); n += 2);
return n;
}
int HashFunc(int k, int s) {
return k % 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 = nextPrime(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 pos = HashFunc(k, ht->s);
int collisions = 0;
while (ht->t[pos].info != Emp && ht->t[pos].e != k) {
pos = pos + 2 * ++collisions -1;
if (pos >= ht->s)
pos = pos - ht->s;
}
return pos;
}
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;
}
}
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;
}
void display(HashTable *ht) {
for (int i = 0; i < ht->s; i++) {
int value = ht->t[i].e;
if (!value)
cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
else
cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;
}
}
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 The 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);
cout<<"Size of Hash Table: "<<nextPrime(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 The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 4 Table Size is Too Small Size of Hash Table: 51.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The Table 5.Exit Enter your choice: 1 Enter size of the Hash Table: 10 Size of Hash Table: 111.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The 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 The Table 5.Exit Enter your choice: 2 Enter element to be inserted: 2 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The 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 The 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 The 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 The 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 The 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 The 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 The 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 The 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 The 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 The 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 The Table 5.Exit Enter your choice: 3 Position: 1 Element: 11 Position: 2 Element: 1 Position: 3 Element: 2 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 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The 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 The Table 5.Exit Enter your choice: 3 Position: 1 Element: Null Position: 2 Element: 1 Position: 3 Element: 2 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 Position: 21 Element: Null Position: 22 Element: Null Position: 23 Element: Null 1.Initialize size of the table 2.Insert element into the table 3.Display Hash Table 4.Rehash The 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 The Table 5.Exit Enter your choice: 5