# C++ Program to Implement Hash Tables with Quadratic Probing

This C++ Program demonstrates operations on Hash Tables with Quadratic Probing.

Here is source code of the C++ Program to demonstrate Hash Tables with Quadratic Probing. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C++ Program to Implement Hash Tables with Quadratic Probing`
3. ` */`
4. `#include <iostream>`
5. `#include <cstdlib>`
6. `#define MIN_TABLE_SIZE 10`
7. `using namespace std;`
8. `/*`
9. ` * Node Type Declaration`
10. ` */`
11. `enum EntryType {Legitimate, Empty, Deleted};`
12. `/*`
13. ` * Node Declaration`
14. ` */`
15. `struct HashNode`
16. `{`
17. `    int element;`
18. `    enum EntryType info;`
19. `};`
20. `/*`
21. ` * Table Declaration`
22. ` */`
23. `struct HashTable`
24. `{`
25. `    int size;`
26. `    HashNode *table;`
27. `};`
28. `/*`
29. ` * Returns whether n is prime or not`
30. ` */`
31. `bool isPrime (int n)`
32. `{`
33. `    if (n == 2 || n == 3)`
34. `        return true;`
35. `    if (n == 1 || n % 2 == 0)`
36. `        return false;`
37. `    for (int i = 3; i * i <= n; i += 2)`
38. `        if (n % i == 0)`
39. `            return false;`
40. `    return true;`
41. `}`
42. `/*`
43. ` * Finding next prime size of the table`
44. ` */`
45. `int nextPrime(int n)`
46. `{`
47. `    if (n <= 0)`
48. `        n == 3;`
49. `    if (n % 2 == 0)`
50. `        n++;`
51. `    for (; !isPrime( n ); n += 2);`
52. `    return n;`
53. `}`
54. `/*`
55. ` * Function To Generate Hash`
56. ` */`
57. `int HashFunc(int key, int size)`
58. `{`
59. `    return key % size;`
60. `}`
61. `/*`
62. ` * Function to Initialize Table`
63. ` */`
64. `HashTable *initializeTable(int size)`
65. `{`
66. `    HashTable *htable;`
67. `    if (size < MIN_TABLE_SIZE)`
68. `    {`
69. `        cout<<"Table Size Too Small"<<endl;`
70. `        return NULL;`
71. `    }`
72. `    htable = new HashTable;`
73. `    if (htable == NULL)`
74. `    {`
75. `        cout<<"Out of Space"<<endl;`
76. `        return NULL;`
77. `    }`
78. `    htable->size = nextPrime(size);`
79. `    htable->table = new HashNode [htable->size];`
80. `    if (htable->table == NULL)`
81. `    {`
82. `        cout<<"Table Size Too Small"<<endl;`
83. `        return NULL;`
84. `    }`
85. `    for (int i = 0; i < htable->size; i++)`
86. `    {`
87. `        htable->table[i].info = Empty;`
88. `        htable->table[i].element = NULL;`
89. `    }`
90. `    return htable;`
91. `}`
92. `/*`
93. ` * Function to Find Element at a key`
94. ` */`
95. `int Find(int key, HashTable *htable)`
96. `{`
97. `    int pos = HashFunc(key, htable->size);`
98. `    int collisions = 0;`
99. `    while (htable->table[pos].info != Empty &&`
100. `           htable->table[pos].element != key)`
101. `    {`
102. `        pos = pos + 2 * ++collisions -1;`
103. `        if (pos >= htable->size)`
104. `            pos = pos - htable->size;`
105. `    }`
106. `    return pos;`
107. `}`
108. `/*`
109. ` * Function to Insert Element into a key`
110. ` */`
111. `void Insert(int key, HashTable *htable)`
112. `{`
113. `    int pos = Find(key, htable);`
114. `    if (htable->table[pos].info != Legitimate)`
115. `    {`
116. `        htable->table[pos].info = Legitimate;`
117. `        htable->table[pos].element = key;`
118. `    }`
119. `}`
120. `/*`
121. ` * Function to Rehash the Table`
122. ` */`
123. `HashTable *Rehash(HashTable *htable)`
124. `{`
125. `    int size = htable->size;`
126. `    HashNode *table = htable->table;`
127. `    htable = initializeTable(2 * size);`
128. `    for (int i = 0; i < size; i++)`
129. `    {`
130. `        if (table[i].info == Legitimate)`
131. `            Insert(table[i].element, htable);`
132. `    }`
133. `    free(table);`
134. `    return htable;`
135. `}`
136. `/*`
137. ` * Function to Retrieve Hash Table`
138. ` */`
139. `void Retrieve(HashTable *htable)`
140. `{`
141. `    for (int i = 0; i < htable->size; i++)`
142. `    {`
143. `        int value = htable->table[i].element;`
144. `        if (!value)`
145. `            cout<<"Position: "<<i + 1<<" Element: Null"<<endl;`
146. `        else`
147. `            cout<<"Position: "<<i + 1<<" Element: "<<value<<endl;`
148. `    }`
149. ` `
150. `}`
151. `/*`
152. ` * Main Contains Menu`
153. ` */`
154. `int main()`
155. `{`
156. `    int value, size, pos, i = 1;`
157. `    int choice;`
158. `    HashTable *htable;`
159. `    while(1)`
160. `    {`
161. `        cout<<"\n----------------------"<<endl;`
162. `        cout<<"Operations on Quadratic Probing"<<endl;`
163. `        cout<<"\n----------------------"<<endl;`
164. `        cout<<"1.Initialize size of the table"<<endl;`
165. `        cout<<"2.Insert element into the table"<<endl;`
166. `        cout<<"3.Display Hash Table"<<endl;`
167. `        cout<<"4.Rehash The Table"<<endl;`
168. `        cout<<"5.Exit"<<endl;`
169. `        cout<<"Enter your choice: ";`
170. `        cin>>choice;`
171. `        switch(choice)`
172. `        {`
173. `        case 1:`
174. `            cout<<"Enter size of the Hash Table: ";`
175. `            cin>>size;`
176. `            htable = initializeTable(size);`
177. `            cout<<"Size of Hash Table: "<<nextPrime(size);`
178. `            break;`
179. `        case 2:`
180. `            if (i > htable->size)`
181. `            {`
182. `                cout<<"Table is Full, Rehash the table"<<endl;`
183. `                continue;`
184. `            }`
185. `        	cout<<"Enter element to be inserted: ";`
186. `        	cin>>value;`
187. `            Insert(value, htable);`
188. `            i++;`
189. `            break;`
190. `        case 3:`
191. `            Retrieve(htable);`
192. `            break;`
193. `        case 4:`
194. `            htable = Rehash(htable);`
195. `            break;`
196. `        case 5:`
197. `            exit(1);`
198. `        default:`
199. `           cout<<"\nEnter correct option\n";`
200. `       }`
201. `    }`
202. `    return 0;`
203. `}`

```\$ g++ Quadratic_Probing.cpp
\$ a.out
----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter size of the Hash Table: 5
Table Size Too Small
Size of Hash Table: 5
----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter size of the Hash Table: 10
Size of Hash Table: 11
----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 100

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 200

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 300

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 400

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 500

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 600

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 700

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 800

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 900

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 1000

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 1100

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
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
Position: 1 Element: 1100
Position: 2 Element: 100
Position: 3 Element: 200
Position: 4 Element: 300
Position: 5 Element: 400
Position: 6 Element: 500
Position: 7 Element: 600
Position: 8 Element: 700
Position: 9 Element: 800
Position: 10 Element: 900
Position: 11 Element: 1000

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: Null
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: Null
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: Null
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: Null
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
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 element to be inserted: 2200

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 3300

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 4400

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 5500

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Enter element to be inserted: 6600

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit
Position: 1 Element: Null
Position: 2 Element: 300
Position: 3 Element: 600
Position: 4 Element: 900
Position: 5 Element: 5500
Position: 6 Element: Null
Position: 7 Element: Null
Position: 8 Element: 4400
Position: 9 Element: 100
Position: 10 Element: 400
Position: 11 Element: 700
Position: 12 Element: 1000
Position: 13 Element: 3300
Position: 14 Element: Null
Position: 15 Element: Null
Position: 16 Element: 2200
Position: 17 Element: 200
Position: 18 Element: 500
Position: 19 Element: 800
Position: 20 Element: 1100
Position: 21 Element: Null
Position: 22 Element: Null
Position: 23 Element: 6600

----------------------

----------------------
1.Initialize size of the table
2.Insert element into the table
3.Display Hash Table
4.Rehash The Table
5.Exit

------------------
(program exited with code: 1)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.