Assignment No: 01

Name : Om Santosh Songire

Roll no: SE_B_128

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

Program :

#include<iostream>
using namespace std;

const int TABLE_SIZE=10;

struct Client
{
string name;
string phone;
bool occupied;

Client() {occupied = false; }

};

class HashTable
{
private:
Client table[TABLE_SIZE];
int ProbingType;

int HashFunction(string key)

{
int HashValue=0;
for(size_t i=0;i<key.length();i++)
{
HashValue+=key[i];
}
return HashValue % TABLE_SIZE;
}
public:
HashTable(int type)
{
ProbingType=type;
}

void insert(string name, string phone)

{
int index=HashFunction(name);
int i=0;

while(table[index].occupied)
 {
i++;
index = (ProbingType==0) ? (index+1)% TABLE_SIZE
: (index+i*i)%
TABLE_SIZE;
if(i>=TABLE_SIZE)
{
cout<<"Table is full!\n";
return;
}
}
table[index].name=name;
table[index].phone=phone;
table[index].occupied=true;
cout<<"\nInserted Successfully!!\n";
}

void search(string name)

{
int index=HashFunction(name);
int i=0, comparisons=0;

while(table[index].occupied)
{
comparisons++;
if(table[index].name==name)
{
cout<<"Found: "<<table[index].phone<<" (Comparisons:
"<<comparisons<<" )\n";
return;
}
i++;
index=(ProbingType==0) ? (index+1)% TABLE_SIZE
: (index+i*i)% TABLE_SIZE;
if (i>=TABLE_SIZE) break;
}
cout<<"Client not found!! (Comparisons: "<<comparisons<<" )";
}

void display()
{
cout<<"\nHash Table:\n";
for(int i=0;i<TABLE_SIZE;i++)
{
if(table[i].occupied)
{
cout<<"["<<i<<"] "<<table[i].name<<" ->
"<<table[i].phone<<"\n";
}
else
{
cout<<"["<<i<<"] --empty--\n";
 }
}
}
};

int main()
{
int choice, ProbingType;
cout << "Choose Collision Handling:\n1. Linear Probing\n2. Quadratic Probing\n";
cin >> choice;
ProbingType = (choice == 1) ? 0 : 1;

HashTable PhoneBook(ProbingType);

while (true) {
cout << "\nMenu:\n1. Insert Client\n2. Search Client\n3. Display Table\n4. Exit\nEnter choice:
";
cin >> choice;
cin.ignore();

if (choice == 1) {
string name, phone;
cout << "Enter Name: ";
getline(cin, name);
cout << "Enter Phone: ";
getline(cin, phone);
PhoneBook.insert(name, phone);
}
else if (choice == 2) {
string name;
cout << "Enter Name to Search: ";
getline(cin, name);
PhoneBook.search(name);
}
else if (choice == 3) {
PhoneBook.display();
}
else if (choice == 4) {
break;
}
else {
cout << "Invalid Choice! Try again.\n";
}
}
return 0;
}
Output :

(base) comp-proj-sys04@compprojsys04-OptiPlex-3010:~$ g++ dsal1.cpp

(base) comp-proj-sys04@compprojsys04-OptiPlex-3010:~$ ./a.out
Choose Collision Handling:
1. Linear Probing
2. Quadratic Probing
1

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 1
Enter Name: Om
Enter Phone: 8793899

Inserted Successfully!!

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 2
Enter Name to Search: Om
Found: 8793899 (Comparisons: 1 )

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 3

Hash Table:
[0] --empty--
[1] --empty--
[2] --empty--
[3] --empty--
[4] --empty--
[5] --empty--
[6] --empty--
[7] --empty--
[8] Om -> 8793899
[9] --empty--

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 4
(base) comp-proj-sys04@compprojsys04-OptiPlex-3010:~$ g++ dsal1.cpp
(base) comp-proj-sys04@compprojsys04-OptiPlex-3010:~$ ./a.out
Choose Collision Handling:
1. Linear Probing
2. Quadratic Probing
2

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 1
Enter Name: Om
Enter Phone: 8793899

Inserted Successfully!!

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 3

Hash Table:
[0] --empty--
[1] --empty--
[2] --empty--
[3] --empty--
[4] --empty--
[5] --empty--
[6] --empty--
[7] --empty--
[8] Om -> 8793899
[9] --empty--

Menu:
1. Insert Client
2. Search Client
3. Display Table
4. Exit
Enter choice: 4