Question

C++.

You are to write a program to set up a data base for a phone index. The key will be a person’s name and the table will supply the phone number. The data base must be implemented as a hash table with the names as the key. The format will be a person name (multiple parts) followed by a phone number. Example:   John Doe   601-5433   or O E Vay 921-1234. Only one name one phone number will be on an input line.

Set your hash table up to be 15 entries, hash table is 15 in size.

1. Print out the final data base (hash table) and indicate how many collisions were made in building the data base.

2.   After building the Phone Index, show examples of looking up a name and returning a phone number. Also show examples of looking up a name that are not in the table.

You are to come up with your own hash function. You are to have very few collisions. A large number of collisions will reduce your grade on this assignment.

INPUT FILE:

stephens reynolds 696-9231
mack russell 123-1234
Lewis Michelle Tee 828-2148
john marshall 888-2891
Mister Rogers 924-7221
Hasey Moto 823-8000
Snow White       111-9999
Oe vey 177-1423
Twoseeor knocksee 823-8321
Legg T. 587-2839
Znot Noz Oozey 531-4353
Hofstra M. 601-3225
Malioneyh P. J. 287-4344
Morier G. E. 544-2319
Cray Z. Cyco 134-7242

Answer 1

Hi,

Please find code below.

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<math.h>
#include<unordered_set>

using namespace std;

const int totalPhoneNos = 15;
int collisions = 0;
std::unordered_set<long> alreadyEncounteredHashVal;

class PhoneBookHashTable {
public:
string keyName;
string phoneNum;
PhoneBookHashTable(string keyName, string phoneNum) {
this->keyName= keyName;
this->phoneNum = phoneNum;
}
};
class PhoneBook
{
private:
PhoneBookHashTable **PB;
public:
PhoneBook()
{
alreadyEncounteredHashVal.reserve(15);
PB = new PhoneBookHashTable * [totalPhoneNos];
for (int i = 0; i< totalPhoneNos; i++) {
PB[i] = NULL;
}
}
int myHashFunc(string k)
{
unsigned myFinalHashValue = 0;
for (int x = 0; x < k.length(); ++x)
{
myFinalHashValue ^= (myFinalHashValue << 5) +
(myFinalHashValue >> 2) +
k[x];
}
cout << "hash return value: " << myFinalHashValue % 15 << endl;
return myFinalHashValue % 15; // I'm using 15 here so that my array shouldnt exceed 15 index.
// then we might get array index out of bound errors.
}
void InsertPhoneEntry(string k, string v)
{
cout << "coming to insert phone entry" << endl;
int h = myHashFunc(k);
auto i = alreadyEncounteredHashVal.find(h);
if (i == alreadyEncounteredHashVal.end())
{
alreadyEncounteredHashVal.emplace_hint(i, h);
}
else
{
++collisions;
}
while (PB[h] != NULL && PB[h]->keyName != k)
{
h = myHashFunc(PB[h + 1]->keyName);
}
if (PB[h] != NULL)
delete PB[h];
PB[h] = new PhoneBookHashTable(k, v);
}
string SearchNameinPhoneBook(string key)
{
cout << "SearchNameinPhoneBook" << endl;
int h = myHashFunc(key);
cout << " hash Function:" << h << endl;
auto i = alreadyEncounteredHashVal.find(h);
if (i == alreadyEncounteredHashVal.end())
{
alreadyEncounteredHashVal.emplace_hint(i, h);
}
else
{
++collisions;
}
while (PB[h] != NULL && PB[h]->keyName != key)
{
h = myHashFunc(PB[h + 1]->keyName);
}
if (PB[h] == NULL)
return "not-in-table";
else
return PB[h]->phoneNum;
}
void printBook()
{
int h =0;
while(PB[h]!= NULL && h <=15)
{
cout << "key: " << PB[h]->keyName << "phno: " << PB[h]->phoneNum << endl;
h++;
}
cout << " No of collisions:" << collisions << endl;
}
~PhoneBook()
{
for (int i = 0; i < totalPhoneNos; i++) {
if (PB[i] != NULL)
delete PB[i];
delete[] PB;
}
}
};
int main()
{
PhoneBook newPhoneBook;
string name, phNo;
int c;
while (1) {
cout<<"1.Insert entry into the phone book table"<<endl;
cout<<"2.Search element from the persons name"<<endl;
cout<<"3.print whole book"<<endl;
cout<<"4.Exit"<< endl;
cout<<"Enter your choice: ";
cin>>c;
switch(c) {
case 1:
cout<<"Enter name to be inserted: ";
//cin.ignore();
//std::getline(std::cin, name);
std::getline(std::cin >> std::ws, name);
cout<<"Enter key at which element to be inserted: ";
//cin.ignore();
//std::getline(std::cin, phNo);
std::getline(std::cin >> std::ws, phNo);
newPhoneBook.InsertPhoneEntry(name, phNo);
break;
case 2:
cout<<"Enter key of the element to be searched: ";
std::getline(std::cin >> std::ws, name);
if (newPhoneBook.SearchNameinPhoneBook(name) == "not-in-table")
{
cout<<"No phone number against name "<< name <<endl;
continue;
}
else
{
cout<<"phone number for name "<< name <<" : ";
cout<<newPhoneBook.SearchNameinPhoneBook(name)<<endl;
}
break;
case 3:
cout << "Printing whole phonebook " << endl;
newPhoneBook.printBook();
break;
case 4:
exit(1);
default:
cout<<"\nPlease enter valid option\n";
}
}
return 0;
}
1.Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 14.Exit Enter your choice: 1 Enter name to be inserted: stephen reynolds Enter key at which element to be inserted: 123-456 coming to insert phone entry hash return value: 0 1. Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 4.Exit Enter your choice: 3 Printing whole phonebook key: stephen reynoldsphno: 123-456 No of collisions:0 1. Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 4. Exit Enter your choice: 2 Enter key of the element to be searched: stephen reynolds SearchNameinPhoneBook hash return value: 0 hash Function:0 phone number for name stephen reynolds : SearchNameinPhoneBook hash return value: 0 hash Function:0 123-456

1.Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 4.Exit Enter your choice: 1 Enter name to be inserted: mack russel Enter key at which element to be inserted: 456-789 coming to insert phone entry hash return value:10 1. Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 4.Exit Enter your choice: 2 Enter key of the element to be searched: amruth SearchNameinPhoneBook hash return value:5 hash Function:5 No phone number against name amruth, 1. Insert entry into the phone book table 2. Search element from the persons name 3.print whole book 4. Exit Enter your choice: I
Thanks,

kindly upvote