Help Write Hash Program Two keys: Name or Phone Nbrs You are to write a program
ID: 3760451 • Letter: H
Question
Help Write
Hash Program
Two keys: Name or Phone Nbrs
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 input data file is out on blackboard. 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 31 entries, hash table is 31 in size.
Print out the final data base (hash table) and indicate how many collisions were made in building the data base.
After building the Phone Index, show examples of looking up a name and returning a phone number.
Now I do have some folks (police usually) that have a phone number but need to know the person. So you will create a second hash key capability to use the phone number (hashed) as a key to the data base. Now you ca not create a new hash table since it is anticipated that the table will become quite large and there is only room for one copy. You can though create an index table to access the data base.
3. Print out the data base (names and phone numbers (hash table)) in the order of the phone hash keys.
4. Now test your phone number look up and show that it works again return the name and phone number.
Explanation / Answer
Answer:
Program code to copy:
// NameAndPhonephonenumber-Hashtable.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<fstream>
using namespace std;
int hash_func(string a)
{
unsigned long long int h = 7;
for(int i = 0; i < a.length(); i++)
{
h = ((h * 31) + a[i]);
}
return h % 31;
}
int hash_Phfunc(string a)
{
unsigned long long int h = 7;
for(int i = 0; i < a.length(); i++)
{
if(a[i] == '-')
continue;
else
h = (h * 31) + a[i] - '0';
}
return (h % 31);
}
int main()
{
ifstream file;
file.open("PhoneIndex.txt");
string names[1000], phonenum[1000];
string line;
int i = 0;
while(!file.eof())
{
getline(file, line, ' ');
names[i] = line;
getline(file, line);
phonenum[i] = line;
i++;
}
int sz = i;
file.close();
vector< pair<string, string> > hash[31];
int visited[31] = {0};
int coll = 0;
for(int i = 0; i < sz; i++)
{
int n = hash_func(names[i]);
if(visited[n] == 1)
{
coll++;
hash[n].push_back(make_pair(names[i], phonenum[i]));
}
else
{
hash[n].push_back(make_pair(names[i], phonenum[i]));
visited[n] = 1;
}
}
cout << " Print the phone data base ";
for(int i = 0; i < 31; i++)
{
cout << i << " -> ";
for(unsigned int j = 0; j < hash[i].size(); j++)
{
cout << "{ " << hash[i][j].first << ", " << hash[i][j].second << " }" << " ";
}
cout << endl << endl;
}
cout << "Number of collisions " << coll << endl << endl;
string search_name;
cout << " Enter the name of user to be searched ";
getline(cin, search_name);
int flag = 0;
int n = hash_func(search_name);
for(int i = 0; i < hash[n].size(); i++)
{
if(hash[n][i].first.compare(search_name) == 0)
{
cout << "Phone number of " << search_name << " is " << hash[n][i].second << endl << endl;
flag = 1;
}
}
if(flag == 0)
cout << search_name << " is not found in the database ";
visited[31] = {0};
vector<pair<string, string> > hashIndex[31];
cout << " ******************************************** " << endl<<endl;
cout << "List of phone number details by using phone number as key:" << endl << endl;
for(int j = 0; j < 31; j++)
{
for(unsigned int k = 0; k < hash[j].size(); k++)
{
int has1 = hash_Phfunc(hash[j][k].second);
if(visited[has1] == 1)
{
hashIndex[has1].push_back(make_pair(hash[j][k].first, hash[j][k].second));
}
else
{
hashIndex[has1].push_back(make_pair(hash[j][k].first, hash[j][k].second));
visited[n] = 1;
}
}
}
int val = 0;
for(int i = 0; i < 11; i++)
{
cout << i << " -> ";
for(unsigned int j = 0; j < hashIndex[i].size(); j++)
{
cout << "{" << hashIndex[i][j].first << "," << hashIndex[i][j].second <<
"} ";
}
cout << endl;
}
cout << " Enter the phoneNumber of user to be searched ";
getline(cin, search_name);
flag = 0;
n = hash_Phfunc(search_name);
for(int i = 0; i < hashIndex[n].size(); i++)
{
if(hashIndex[n][i].second.compare(search_name) == 0)
{
cout << "Name of the phone number" << search_name << " is " << hashIndex[n][i].first << endl << endl;
flag = 1;
}
}
if(flag == 0)
cout << search_name << " is not found in the database ";
system("pause");
return 0;
}
Sample Output:
Print the phone data base
0 ->
1 -> { james wilis thomas, 261-8342 }
2 -> { Twoseeor knocksee, 823-8321 } { Hoos R. Dadie, 818-3821 }
3 ->
4 ->
5 ->
6 ->
7 ->
8 -> { Taylor marie, 939-1512 } { lea high lee, 266-8324 } { Malioneyh P. J., 28
7-4344 } { Mighty Mouse, 222-2222 }
9 ->
10 ->
11 ->
12 ->
13 ->
14 -> { Stone Rock, 544-2372 } { Lewis Michelle Tee, 828-2148 }
15 -> { mack russell, 123-1234 } { Legg T., 587-2839 } { Hofstra M., 601-3225 }
{ Morier G. E., 544-2319 } { Hauser M., 606-2940 } { Currie W. D., 701-4281 } {
Legg T., 857-2839 }
16 ->
17 ->
18 ->
19 ->
20 ->
21 -> { Tobe Cir, 613-2414 } { SixOne Other, 843-2343 }
22 ->
23 -> { TooB OrNot, 283-5214 }
24 -> { john marshall, 888-2891 } { Smelly Tau, 707-7281 }
25 ->
26 -> { Tyosn Chicken, 602-3152 } { Big Tow, 384-5624 } { Zevent Heaven, 834-256
3 }
27 ->
28 -> { stephens reynolds, 696-9231 } { Moto hasey, 823-8000 } { O E Vay, 177-14
23 }
29 ->
30 ->
Number of collisions 17
Enter the name of user to be searched
Moto hasey
Phone number of Moto hasey is 823-8000
********************************************
List of phone number details by using phone number as key:
0 -> {Hauser M.,606-2940} {Moto hasey,823-8000}
1 -> {Twoseeor knocksee,823-8321} {Hoos R. Dadie,818-3821} {Currie W. D.,701-4
281} {john marshall,888-2891} {Smelly Tau,707-7281} {stephens reynolds,696-92
31}
2 -> {james wilis thomas,261-8342} {Taylor marie,939-1512} {Mighty Mouse,222-2
222} {Stone Rock,544-2372} {Tyosn Chicken,602-3152}
3 -> {SixOne Other,843-2343} {Zevent Heaven,834-2563} {O E Vay,177-1423}
4 -> {lea high lee,266-8324} {Malioneyh P. J.,287-4344} {mack russell,123-1234
} {Tobe Cir,613-2414} {TooB OrNot,283-5214} {Big Tow,384-5624}
5 -> {Hofstra M.,601-3225}
6 ->
7 ->
8 -> {Lewis Michelle Tee,828-2148}
9 -> {Legg T.,587-2839} {Morier G. E.,544-2319} {Legg T.,857-2839}
10 ->
Enter the phoneNumber of user to be searched
544-2319
Name of the phone number544-2319 is Morier G. E.
Press any key to continue . . .
Sample Input: PhoneIndex.txt
Taylor marie 939-1512
james wilis thomas 261-8342
Stone Rock 544-2372
lea high lee 266-8324
stephens reynolds 696-9231
mack russell 123-1234
Lewis Michelle Tee 828-2148
john marshall 888-2891
Moto hasey 823-8000
O E Vay 177-1423
Twoseeor knocksee 823-8321
Legg T. 587-2839
Hofstra M. 601-3225
Malioneyh P. J. 287-4344
Morier G. E. 544-2319
Hauser M. 606-2940
Currie W. D. 701-4281
Hoos R. Dadie 818-3821
Smelly Tau 707-7281
Tobe Cir 613-2414
Tyosn Chicken 602-3152
TooB OrNot 283-5214
SixOne Other 843-2343
Big Tow 384-5624
Zevent Heaven 834-2563
Mighty Mouse 222-2222
Legg T. 857-2839
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.