Program Description You will develop a C++ program that reads an input data set consisting of four parts: the first part is a hash table size requested by a user; the second part is a list of cities with its state, population, and geo-location. This part will end with the line InsertionEnd; the third part is a number of commands to follow; and the forth part is a list of commands.

1. After reading in a hash table size requested by a user, a hash table of the size (with open addressing, double-hashing) needs to be created. Each slot of your hash table should be a pointer of the class called City which you will be creating to store each citys name, state, population, and its geo-location (do not store double-quotes used for geolocation), and a number of collisions. Initially each pointer should be NULL.

2. Then by reading each city information line by line, their information needs to be stored in the hash table using a hash function. You will need to design your hash function so that it reduces the number of collisions. You need to specify your hash functions that will be used, i.e., h(k,i), and h_1(k) and h_2(k) using each city name as its key value. The following shows an example of such data for cities:

AL,Mobile,195111,"(30.67762486480, -88.1184482714)"

AK,Anchorage,291826,"(61.14986873100, -149.111113424)"

AZ,Phoenix,1445632,"(33.57241386950, -112.088995222)"

AZ,Scottsdale,217385,"(33.68724936510, -111.865085877)"

AR,Fayetteville,73580,"(36.07121173120, -94.1659600436)"

AR,Fort Smith,86209,"(35.34916926360, -94.3696317306)"

AR,Jonesboro,67263,"(35.82081215380, -90.6794991686)"

CA,Anaheim,336265,"(33.83890769960, -117.857613481)"

3. After the line InsertionEnd, your program needs to print out the content of your hash table. Then a user will enter a number of commands.

4. Each command will be hash_display, hash_search, or hash_max_population. Hash_Display command: With hash_display command, your program needs to display the content of your hash table by listing the content of each index in the following format, by specifying their number of collisions. If a slot if empty, print out none for strings and -- for integers: