Hash.h $($need to fill in more code$)$

$3.$ Assignment Description

You are required to develop a C$++$ program that reads an input data set consisting of the following four $(4)$ parts $($see input$1.$txt for one example$)$

The first part $($first line$)$ is a hash table size.

The second part is a list of HotelBooking objects, this part will end with the line $$InsertionEnd$.$

The third part is a list of commands that need to be executed, such as 'hashLoadFactor', 'hashDisplay', 'hashSearch', 'hashDelete', etc.

The forth part $($last line$)$ is the command 'End' which terminates the program.

$1.$ After reading in a hash table size $($reresented by an integer$),$ a hash table of the size $($collision resolidg by chaining$)$ needs to be created. Each slot of your hash table should be a LinkedList of nodes where each node represents one HotelBooking object. Initially all linked lists should be empty.

$2.$ Then by reading each HotelBooking$$s information line by line, their information needs to be stored inside the hash table using a hash function. In this assignment, you're required to design your own hash function based on each HotelBooking's associative key. Each HotelBooking's associative key is the combination of hotelName, arrivalDate and confirmNum. You should design$/$test your hash function in such a way that it maximumly reduces the number of collisions, i$.$e$.,$ the HotelBooking objects should be evenly distributed into each slot and the length of each linked list should not be too long $($this will be measured by performance ratio defined below$).$

$4.$ Class Description

$4\mathrm{.}1)$ The LinkedList class

struct HotelBooking

$\{$

string hotelName, arrivalDate;

int confirmNum;

struct HotelBooking$*$ next;

$\}$;

For the linked list of HotelBooking $($class LinkedList.h$),$ you need to create a pointer $("$head$")$ that points to the first element of the linked list $($initially it should be set to NULL$).$ Also you need to create the following functions inside the LinkedList class $($within LinkedList.h file$).$ See below for the class definition:

class LinkedList

$\{$

private:

struct HotelBooking$*$ head;

int size;

public:

LinkedList$()$;

~LinkedList$()$;

HotelBooking$*$ getHead$()$;

int getSize$()$;

bool searchBooking$($string hotelName, string arrivalDate, int confirmNum$)$;

bool insertBooking$($string hotelName, string arrivalDate, int confirmNum$)$;

bool deleteBooking$($string hotelName, string arrivalDate, int confirmNum$)$;

void displayList$()$;

$\}$;

Note: for collision resolving by chaining mechnasim, when two or more than two bookings are hashed into the same slot, the newest HotelBooking should always be inserted at the front of the LinkedList.

$4\mathrm{.}2)$ The Hash class

The Hash.h file represents a hash table which is a one dimensional array of LinkedList. See below for the class definition. Note: feel free to add extra auxillary functions if you feel they make your coding easier, but your Hash class must at least contain the following functions.

class Hash

$\{$

private:

LinkedList$*$ hashTable; $//$hashTable is a one$-$dimensional array of LinkedList

int m; $//$slots number of the hash table

public:

Hash$($int size$)$;

~Hash$()$;

bool hashSearch$($string hotelName, string arrivalDate, int confirmNum$)$;

bool hashInsert$($string hotelName, string arrivalDate, int confirmNum$)$;

bool hashDelete$($string hotelName, string arrivalDate, int confirmNum$)$;

double hashLoadFactor$()$;

void hashDisplay$()$;

int hashFunction$($string key$)$;

$\}$;

Attribute$/$Function Attribute$/$Function$\text{'}$s Description

LinkedList$*$ hashTable; This private attribute represents the underline data structure, i$.$e$.$ a hashTable is a dynamically$-$memory$-$allocated one dimensional array of LinkedList $($LinkedList class is defined above already$).$

int m; This private attribute represents the hash table size, i$.$e$.$ number of slots in one dimensional array of hashTable.

Hash$($int size$)$; This is the constructor of Hash class. It will initialize both hashTable and m attributes. Specially hashTable should be initialize to a one dimensional array of size LinkedList.

~Hash$()$; This is the destructor of Hash class. First it need to delete each LinkedList from each slot, it then delete the whole table and release all occupied memory.

bool hashSearch$($string hotelName, string arrivalDate, int confirmNum$)$; Given a HotelBooking's key $($combination of hotelName, arrivalDate and confirmNum$),$ this function first ca