C++ Programming Code Examples C++ > Data Structures Code Examples Program to Implement Hash Tables with Quadratic Probing Program to Implement Hash Tables with Quadratic Probing #include <iostream> #include <cstdlib> #define MIN_TABLE_SIZE 10 using namespace std; /* Node Type Declaration */ enum EntryType {Legitimate, Empty, Deleted}; /* Node Declaration */ struct HashNode { int element; enum EntryType info; }; /* Table Declaration */ struct HashTable { int size; HashNode *table; }; /* Returns whether n is prime or not */ 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; } /* Finding next prime size of the table */ int nextPrime(int n) { if (n <= 0) n == 3; if (n % 2 == 0) n++; for (; !isPrime( n ); n += 2); return n; } /* Function To Generate Hash */ int HashFunc(int key, int size) { return key % size; } /* Function to Initialize Table */ HashTable *initializeTable(int size) { HashTable *htable; if (size < MIN_TABLE_SIZE) { cout<<"Table Size Too Small"<<endl; return NULL; } htable = new HashTable; if (htable == NULL) { cout<<"Out of Space"<<endl; return NULL; } htable->size = nextPrime(size); htable->table = new HashNode [htable->size]; if (htable->table == NULL) { cout<<"Table Size Too Small"<<endl; return NULL; } for (int i = 0; i < htable->size; i++) { htable->table[i].info = Empty; htable->table[i].element = NULL; } return htable; } /* Function to Find Element at a key */ int Find(int key, HashTable *htable) { int pos = HashFunc(key, htable->size); int collisions = 0; while (htable->table[pos].info != Empty && htable->table[pos].element != key) { pos = pos + 2 * ++collisions -1; if (pos >= htable->size) pos = pos - htable->size; } return pos; } /* Function to Insert Element into a key */ void Insert(int key, HashTable *htable) { int pos = Find(key, htable); if (htable->table[pos].info != Legitimate) { htable->table[pos].info = Legitimate; htable->table[pos].element = key; } } /* Function to Rehash the Table */ HashTable *Rehash(HashTable *htable) { int size = htable->size; HashNode *table = htable->table; htable = initializeTable(2 * size); for (int i = 0; i < size; i++) { if (table[i].info == Legitimate) Insert(table[i].element, htable); } free(table); return htable; } /* Function to Retrieve Hash Table */ void Retrieve(HashTable *htable) { for (int i = 0; i < htable->size; i++) { int value = htable->table[i].element; if (!value) cout<<"Position: "<<i + 1<<" Element: Null"<<endl; else cout<<"Position: "<<i + 1<<" Element: "<<value<<endl; } } /* Main Contains Menu */ int main() { int value, size, pos, i = 1; int choice; HashTable *htable; while(1) { cout<<"\n----------------------"<<endl; cout<<"Operations on Quadratic Probing"<<endl; cout<<"\n----------------------"<<endl; 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>>choice; switch(choice) { case 1: cout<<"Enter size of the Hash Table: "; cin>>size; htable = initializeTable(size); cout<<"Size of Hash Table: "<<nextPrime(size); break; case 2: if (i > htable->size) { cout<<"Table is Full, Rehash the table"<<endl; continue; } cout<<"Enter element to be inserted: "; cin>>value; Insert(value, htable); i++; break; case 3: Retrieve(htable); break; case 4: htable = Rehash(htable); break; case 5: exit(1); default: cout<<"\nEnter correct option\n"; } } return 0; }
