Assignment 1
Consider telephone book database of N clients. Make use of a hash table implementation to quickly
look up client‘s telephone number. Make use of two collision handling techniques and compare
them using number of comparisons required to find a set of telephone numbers
#include <iostream>
#include <cstdlib>
using namespace std;
#define SIZE 11 //Hash table of size 10
typedef long long int ll; //long integer to store phone number
int currSize = 0;
int currSize1 = 0;
class DataItem
{
public:
string name;
ll data;
};
DataItem HT[SIZE]; //array of DataItem objects with a size 10
DataItem HT1[SIZE];
//function used to calculate hash value
int hashCode(ll key)
{
return key % SIZE;
}
//function used to display the hash table
void Display()
{
cout<<"\n Hash Table using Linear Probing"<<endl;
for(int i=0; i<SIZE; i++)
cout<<HT[i].name<<"->"<<HT[i].data<<endl;
cout<<"\n Hash Table using Quadratic Probing"<<endl;
for(int i=0; i<SIZE; i++)
cout<<HT1[i].name<<"->"<<HT1[i].data<<endl;
//function is used to insert valur in hash table using linear probing
void Insert(string name, ll phone)
{
if(currSize == SIZE)
{
cout<<"\nHash Table Overflow"<<endl;
return;
}
int hashKey = hashCode(phone);//calculate hash value
while(HT[hashKey].data != 0) //if collision occur then use linear probing
{
hashKey += 1;
hashKey %= SIZE;
if(currSize == SIZE)
{
cout<<"\nHash Table Overflow"<<endl;
return;
}
}
HT[hashKey].name = name;
HT[hashKey].data = phone;
currSize += 1;
}
// Function to insert using quadratic probing
void InsertQuadratic(string name, ll phone)
{
if (currSize1 == SIZE)
{
cout << "\nHash Table Overflow" << endl;
return;
}
int hashKey = hashCode(phone); // Calculate hash value
int j = 1;
while (HT1[hashKey].data != 0) // If collision occurs, use quadratic probing
{
j++;
hashKey = (hashCode(phone) + j * j) % SIZE; // Quadratic probing formula
}
HT1[hashKey].name = name;
HT1[hashKey].data = phone;
currSize1 += 1;
}
//function is used to delete a record from hash table
void Delete(ll phone)
{
int hashKey = hashCode(phone);
int t = hashKey;
while(HT[hashKey].data != phone)
{
hashKey += 1;
hashKey %= SIZE;
if(hashKey == t)
{
cout<<"Contact Not present"<<endl;
return;
}
}
HT[hashKey].name = "";
HT[hashKey].data = 0;
currSize -= 1;
}
//function is used to search a record in hash table
int Search(ll phone)
{
int comparisons = 0; // To track the number of comparisons
int hashKey = hashCode(phone); //calculate hash value
int t = hashKey;
while(HT[hashKey].data != phone)
{
hashKey += 1;
hashKey %= SIZE;
comparisons++; // Increment comparison count
if(hashKey == t)
{
cout<<"Contact Not present"<<endl;
return comparisons;
}
}
comparisons++; // Increment comparison count for successful search
cout<<HT[hashKey].name<<"\t"<<HT[hashKey].data<<endl;
return comparisons;
}
// Function to search for a contact in hash table using quadratic probing
int SearchQuadratic(ll phone)
{
int comparisons1 = 0; // To track the number of comparisons
int hashKey = hashCode(phone); // calculate hash value
int j = 1;
int t = hashKey;
while (HT1[hashKey].data != phone)
{
j++;
comparisons1++; // Increment comparison count
hashKey = (hashCode(phone) + j * j) % SIZE; // quadratic probing formula
if (hashKey == t)
{
cout << "Contact Not present" << endl;
return comparisons1;
}
}
comparisons1++;
cout << HT1[hashKey].name << "\t" << HT1[hashKey].data << endl;
return comparisons1;
}
int main()
{
string name;
int ch;
int comparisons=0;
ll phone;
while(true)
{
cout<<"\n1. Insert Contact using linear probing "<<endl;
cout<<"2. Display all Contacts"<<endl;
cout<<"3. Search Contact using linear probing"<<endl;
cout<<"4. Delete Contact"<<endl;
cout<<"5. Insert Contact using Quadratic probing "<<endl;
cout<<"6. Search Contact using Quadratic probing"<<endl;
cout<<"7. Exit"<<endl;
cout<<"Enter choice: ";
cin>>ch;
switch(ch)
{
case 1: cout<<"Enter name: ";
cin>>name;
cout<<"Enter contact no.: ";
cin>>phone;
Insert(name, phone);
break;
case 2:
Display();
break;
case 3:
cout<<"Enter contact no.: ";
cin>>phone;
comparisons=Search(phone);
cout << "Comparisons required (Linear Probing): " << comparisons <<
endl;
break;
case 4:
cout<<"Enter contact no.: ";
cin>>phone;
Delete(phone);
break;
case 5: cout<<"Enter name: ";
cin>>name;
cout<<"Enter contact no.: ";
cin>>phone;
InsertQuadratic(name, phone);
break;
case 6:
cout<<"Enter contact no.: ";
cin>>phone;
comparisons = SearchQuadratic(phone);
cout << "Comparisons required (Quadratic Probing): " << comparisons << endl;
break;
case 7:
exit(1);
break;
}
}
return 0;
}
