C++ Double Hashing

Program Description

You will develop a C++ program that reads an input data set consisting of three parts: the first part is a hash table size requested by a user; the second part is a list of phone numbers followed by their owner; the third part is an unordered list of phone numbers. Not all phone numbers in the third part will match phone numbers in the second part. The first, second and third parts of the input will be separated by a blank line. 15

480-111-1111 Albert Smith
480-122-2222 Jackson Jones
480-234-5555 Mary Williams
602-123-4444 Diego Brown
602-333-1111 Angel Davies
623-444-2222 Leo Roberts
520-555-4441 Sam Walker
928-888-5432 Logan Wright
623-999-1534 Lee Thompson
623-444-9876 Tony Edwards
928-543-2121 Alex Green

480-111-1110
602-333-1111
480-122-2222
408-234-5555
480-234-5555
602-123-4444
623-444-2222
223-999-1534
520-555-4441
928-888-5432

There will be less than 30 phone numbers.

Design Requirements:

You should create a hash table with open addressing (double hashing, please specify your functions that will be used for the hash function. That is h(k,i) and h_1(k) and h_2(k) ) for the domain names you should make sure that it cannot "fill up" but that it utilizes memory efficiently. You should use a "double hashing" method for the hash function. When hashing domain names, keep statistics on how many keys were hashed and how many collisions there were. You also need to define INSERT and SEARCH functions for the hash table.

Your program needs to read in the first input number and use it as the hash table size. Each slot of your hash table should contain a phone such as "480-111-1111" (which will be its key), the corresponding first name and last name such as "Albert" and “Smith”, and the number of collision occurred to hash that element. After processing phone numbers into your hash table from the second part of the data, print the content of the hash table using their index using the following format:

index phone number fist name last name collision number

0 602-333-1111 Angel Davies 0
1 928-543-2121 Alex Green 0
2 none none none 0
3 480-234-5555 Mary Williams 0
4 480-122-2222 Jackson Jones 0
5 928-888-5432 Logan Wright 2
6 none none none 0
7 none none none 0
8 623-999-1534 Lee Thompson 1
9 602-123-4444 Diego Brown 0
10 623-444-2222 Leo Roberts 0
11 none none none 0
12 623-444-9876 Tony Edwards 1
13 480-111-1111 Albert Smith 0
14 520-555-4441 Sam Walker 0

Then read the third part of the output, and search if each phone number exists in the hash table. If it exists, then print out its owner, and if it does not exists, print “not found”:

480-111-1110 not found
602-333-1111 belongs to Angel Davies
480-122-2222 belongs to Jackson Jones
408-234-5555 not found
480-234-5555 belongs to Mary Williams
602-123-4444 belongs to Diego Brown
623-444-2222 belongs to Leo Roberts
223-999-1534 not found
520-555-4441 belongs to Sam Walker
928-888-5432 belongs to Logan Wright

Implementation/Documentation Requirements:

• You need implement this program using C++ and it has to read from the standard input (from a keyboard).
• Your program needs to compile and execute in general.asu.edu. You need to define Insert and Search functions (name them “insertElement” and “searchElement”, if the number of elements to be added is more than the hash table size, diplay the error message " the table is full", and proceed to the second part where each phone number is searched), and a hash function h together with h1 and h2 clearly in your code.
• Your code should be well documented and commented.
• At the top of your driver file, within a comment, you need to write your hash function by specifying h1 and h2.
• At the top of your driver file, within a comment, write your hash analysis -- how did you come up with your hash function? Was the number of collisions what you expected? Did your h1work well, how about h2? If you had to change your function to reduce the number of collisions, how did you change it?
• You must use the provided data sets.
• Also you are not allowed to use any predefined data structures (such as ones in the library in C++, etc.) except arrays, you need to build your own data structures and operations associated with them (such as Insert or Search).
• Copying any codes from other people's programs is considered to be cheating and will lead to a report to the Dean and you will be penalized.