// CPP program to implement double hashing #include <bits/stdc++.h> using namespace std; // Hash table size #define TABLE_SIZE 13 // Used in second hash function. #define PRIME 7 class DoubleHash { // Pointer to an array containing buckets int *hashTable; int curr_size; public: // function to check if hash table is full bool isFull() { // if hash size reaches maximum size return (curr_size == TABLE_SIZE); } // function to calculate first hash int hash1(int key) { return (key % TABLE_SIZE); } // function to calculate second hash int hash2(int key) { return (PRIME - (key % PRIME)); } DoubleHash() { hashTable = new int[TABLE_SIZE]; curr_size = 0; for (int i=0; i<TABLE_SIZE; i++) hashTable[i] = -1; } // function to insert key into hash table void insertHash(int key) { // if hash table is full if (isFull()) return; // get index from first hash int index = hash1(key); // if collision occurs if (hashTable[index] != -1) { // get index2 from second hash int index2 = hash2(key); int i = 1; while (1) { // get newIndex int newIndex = (index + i * index2) % TABLE_SIZE; // if no collision occurs, store // the key if (hashTable[newIndex] == -1) { hashTable[newIndex] = key; break; } i++; } } // if no collision occurs else hashTable[index] = key; curr_size++; } // function to display the hash table void displayHash() { for (int i = 0; i < TABLE_SIZE; i++) { if (hashTable[i] != -1) cout << i << " --> " << hashTable[i] << endl; else cout << i << endl; } } }; // Driver's code int main() { int a[] = {19, 27, 36, 10, 64}; int n = sizeof(a)/sizeof(a[0]); // inserting keys into hash table DoubleHash h; for (int i = 0; i < n; i++) h.insertHash(a[i]); // display the hash Table h.displayHash(); return 0; }
Output:
0 1 --> 27 2 3 4 5 --> 10 6 --> 19 7 8 9 10 --> 36 11 12 --> 64