Introduction

$*$In C$++$ with doxygen style comments Please$*$ A hash table is a very efficient way to lookup and store data. It is efficient because we can use an algorithm called a hash to create an index into the table. The downside to hashing is the problem with collisions. This happens when two pieces of data hash to the same location. The two most popular methods for dealing with collisions are linear probing and separate chaining.

With linear probing you hash the data to determine the location. If the location has data in it you seek forward until you find an empty place in the table to place the data.

With separate chaining there are a couple of ways to implement the table. One way would be to use an array that could be resized. You would have to use the new operator and come up with a scheme to resize your table. In other words this would be implemented using an array of arrays or a $2$D array. The other way would be to use a vector $($C$++)$ or and ArrayList $($Java$).$This would be implemented as a vector of vectors or a vector of linked lists.

Your Task $-$ An Application Of A Hash Table

For this task you will devises a separate chaining scheme to lookup and store telephone numbers. To handle the separate chaining you are to create your table as a vector $($C$++)/$ ArrayList $($java$)$ of PairLists. You should use the same PairList you created in an earlier project. Since there are two pieces of data to store $($name $/$ phone number$)$ the PairList seems like a good choice for the task at hand.

The Input to your program will be a simple text file that contains the names and phone numbers. You are to use the file attached below. When the program begins it should read the file and load the data into a hash table. Please do not have your program ask for the name and or path to the file. Simply load it$.$ The data should be hashed by the name not the number. basically you are using the name as the key and the phone number for the value. Once the hashed index is determined add the data to the end of the PairList at that location.

You should also provide functionality that will allow a name to be input and the phone number retrieved and displayed. This should also include an appropriate message when the user does not exist in the table.

For this assignment you are going to set the table size to $53$ because it is a nice prime number. In addition, you can expect to have names that will hash to the same value. You must make sure your collision avoidance scheme is working properly.

For this assignment I would expect to see the following classes

Pair

PairList

LinkedList

HashTable

along with a main function that is clearly marked.

Public HashTable Functionality:

HashTable$()-$ default constructor

add$($string name, string number$)-$ Adds the name and number to the hash table

printTable$()-$ prints out the entire table and should show the hashed location of each Pair in the table.

string lookup$($string name$)-$ returns a formatted string that contains the data to be output

From main create functionality to read in the text file, parse the input, and add the data to the hash table by calling the add function. Once the table is loaded create a simple menu that will allow the user to either print the entire table formatted properly by showing the name, phone number, and hash value along with the offset of each hash value as follows:

Micheal $(43-1)(555)973-2120$

Or lookup a number. This will allow the user to input a name and output the corresponding phone number. This functionality should also output the hash value. The output from this menu selection should look like the following:

Enter name: Liam

Liam $(38-0)(555)973-1234$

Look up another number y

Enter Name: Rene

Rene $(43-0)(555)973-2083$

Look up another number y

Enter Name: Micheal

Micheal $(43-1)(555)973-2120$

Using the Bernstein hash function with a table size of $53$ Rene and Micheal hash to the same value. When this occurs you should output the hash location and the offset where the value as been probed to$.$ Data Text to be used Liam; $(555)973-1234$;

Noah; $(555)973-1235$;

William; $(555)973-1236$;

James; $(555)973-1237$;

Logan; $(555)973-1238$;

Benjamin; $(555)973-1239$;

Mason; $(555)973-1240$;

Elijah; $(555)973-1241$;

Oliver; $(555)973-1242$;

Jacob; $(555)973-1243$;

Lucas; $(555)973-1244$;

Michael; $(555)973-1245$;

Alexander; $(555)973-1246$;

Ethan; $(555)973-1247$;

Daniel; $(555)973-1248$;

Matthew; $(555)973-1249$;

Aiden; $(555)973-1250$;

Henry; $(555)973-1251$;

Joseph; $(555)973-1252$;

Jackson; $(555)973-1253$;

Samuel; $(555)973-1254$;

Sebastian; $(555)973-1255$;

David; $(555)973-1256$;

Carter; $(555)973-1257$;

Wyatt; $(555)973-1258$;

Jayden; $(555)973-1259$;

John; $(555)973-1260$;

Owen; $(555)973-1261$;

Dylan; $(555)973-1262$;

Luke; $(555)973-1263$;

Gabriel; $(555)973-1264$;

Anthony; $(555)973-1265$;

Isaac; $(555)973-1266$;

Grayson; $(555)973-1267$;

Jack; $(555)973-1268$;

Julian; $(555)973-1269$;

Levi; $(555)973-1270$;

Christopher; $(555)973-1271$;

Joshua; $(555)$