I have this code below, and I need to implement this program to demonstrate quad
ID: 3711704 • Letter: I
Question
I have this code below, and I need to implement this program to demonstrate quadratic hash probing when a collision occurs.
The language is C++
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
int main(){
string data[100];
int n;
string str;
int count = 0;
for (int i = 0; i<100; i++)
data[i] = "-1";
while(true){
cout << "1.Insert key ";
cout << "2.delete key ";
cout << "3.Display Hash Table ";
cout << "4.Exit ";
cout << "Enter choice:";
cin >> n;
if (n == 4){
break;
}
if (n == 1){
if (count < 100){
cout << "Enter key:";
cin >> str;
int sum = 0;
for (int i = 0; i<str.size(); i++)
sum = sum + str[i];
int index = sum % 100;
if (data[index] == "-1"){
data[index] = str;
cout << "Key inserted ";
count++;
}
else {
cout << "Its a collision ";
}
}
else {
cout << "Hash table is full ";
}
}
if (n == 2){
cout << "Enter key:";
cin >> str;
int sum = 0;
for (int i = 0; i<str.size(); i++)
sum = sum + str[i];
int index = sum % 100;
data[index] = "-1";
count--;
}
if (n == 3){
cout << setw(10) << "Index" << setw(10) << "Key" << endl;
for (int i = 0; i<100; i++){
if (data[i] != "-1")
cout << setw(10) << i << setw(10) << data[i] << endl;
}
}
}
}
Explanation / Answer
c++ code:
#include<iostream>
#include<string>
#include<iomanip>
using namespace std;
int main(){
string data[100];
int n;
string str;
int count = 0;
int i;
int sum, index;
for (i = 0; i<100; i++)
data[i] = "-1";
while(true){
cout << "1.Insert key ";
cout << "2.delete key ";
cout << "3.Display Hash Table ";
cout << "4.Exit ";
cout << "Enter choice:";
cin >> n;
if (n == 4){
break;
}
if (n == 1){
if (count < 100){
cout << "Enter key:";
cin >> str;
sum = 0;
for (i = 0; i<str.size(); i++)
sum = sum + str[i];
index = sum % 100;
if (data[index] == "-1"){
data[index] = str;
cout << "Key inserted ";
count++;
}
/*collision detected*/
else {
cout << "collision!!! finding the alternative index by quadratic probing ";
i = 1;
while((index = index + i*i - (i-1) * (i-1)) < 100)
{
if (data[index] == "-1")
{
data[index] = str;
cout << "Key inserted ";
count++;
break;
}
i++;
}
if (index >= 100)
cout << "Collision cann't be resolved. ";
}
}
else {
cout << "Hash table is full ";
}
}
if (n == 2){
cout << "Enter key:";
cin >> str;
sum = 0;
for (i = 0; i<str.size(); i++)
sum = sum + str[i];
index = sum % 100;
i = 0;
while(++i)
{
if (str == data[index])
{
data[index] = "-1";
count--;
break;
}
index = index + i * i - (i-1) * (i-1);
if (index >= 100)
break;
}
if (index >= 100)
cout << "Key not found ";
}
if (n == 3){
cout << setw(10) << "Index" << setw(10) << "Key" << endl;
for (i = 0; i<100; i++){
if (data[i] != "-1")
cout << setw(10) << i << setw(10) << data[i] << endl;
}
}
}
}
Output shown after running this code:
$ g++ main.cpp
$ ./a.out
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:1
Enter key:roh
Key inserted
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:1
Enter key:ohr
collision!!! finding the alternative index by quadratic probing
Key inserted
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:3
Index Key
29 roh
30 ohr
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:1
Enter key:hor
collision!!! finding the alternative index by quadratic probing
Key inserted
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:3
Index Key
29 roh
30 ohr
33 hor
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:2
Enter key:hor
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:3
Index Key
29 roh
30 ohr
1.Insert key
2.delete key
3.Display Hash Table
4.Exit
Enter choice:4