1. Implement a dictionary using a hash table with these specifications: - For collision resolution it uses either quadratic hashing or double hashing. - The table size should between 2 times and 4 times the number of lines in the dictionary file. o It cannot be more than 4 times the number of lines in the file. o It can be hardcoded to a number that works well for the data in the Spanish.txt file. o Hint: You may want to use a prime number for the size of your hash table. - It must use a good function for hashing strings. You may use any resource for this function but you must cite it. You are allowed to use code you find on the web for this function alone, but you must cite it. 2. After the table is created display the statistics for building it. (Details will be provided below.) 3. Allow the user to use and update the dictionary through these operations: search, insert, delete, quit. Each operation (with all its needed data) will be given on one line as follows: Line Explanation and behavior q q - Quit Ends the loop that allows the user operations. s word s - Search Will search the dictionary for word. It will display the number of probes the search took. If found, will display the translation. If not found will display a message d word d - Delete Will search the dictionary for word. If found it will remove it. If not found it will display a message. i word newTransl i - Insert It will search the dictionary for word. If found, it will update the existing translation by appending ; and newTransl. If not found it will add this new entry to the dictionary. You can assume that newTransl is a single word of at most 100 characters. For example el gato cannot be given as a new translation for insertion in this loop because it consists of two words. You can assume that for all operations above, word is at most 100 characters, and the operation (s/d/i/q) will have at most 2 characters. 4. Report the statistics for the user operations. (E.g. if the user performed 10 dictionary operations (insert, delete, or search), report the average number of probes per operation. Given files Spanish.txt dictionary data. This is a data file that contains English words and their corresponding Spanish translation. This file name should NOT be hardcoded. The program will take the file name as user input. (Citation for the Spanish.txt file: #Copyright 1999 The Internet Dictionary Project/Tyler Chambers #http://www.june29.com/IDP/. Original file: Spanish_orig.txt) - The maximum size of a line in the dictionary file is 1000. - The maximum size of a query word (that will be used as a key in the dictionary) is 100. - The lines in the dictionary file (e.g. Spanish.txt) have the format: word tab translation - The translation may contain more than one word like in this line for abandon: abandon desamparar, desertar, renunciar, evacuar, repudiar input1.txt Your program must work with this file using input redirection ( < input1.txt). It provides the dictionary file name and a sequence of user operations on the built dictionary. run1.txt - sample run file. Dealing with duplicates The dictionary file may contain duplicates: there may be several lines for the same word. E.g. in Spanish.txt: aback hacia atras aback hacia atrs,take aback, desconcertar. En facha. aback por sopresa, desprevenidamente, de improviso aback atra/s[Adverb] When trying to insert an entry in the hash table, if there is already another entry for that word, APPEND the new translation (from the new entry) to the existing translation in the hash table. For example after loading the Spanish file, when searching for aback, the translation will have the concatenation of all four translations, separated by a ; (shown yellow highlight): hacia atras;hacia atrs,take aback, desconcertar. En facha.;por sopresa, desprevenidamente, de improviso;atra/s[Adverb] Table statistics As you build the hash table, keep track of the following statistics and display them after the table is built (but before the user operations): - the total number of items that could not be hashed. All items must be hashed, so this number should be 0 every time. - the total number of probes required to hash all objects, - the average number of probes required to hash all objects, - the largest number of probes required by any of the keys in the file to be hashed, - an array that at index i stores the count of keys that required i probes to be hashed. In the posted sample run, I printed the count of objects that required up to 100 probes. Self-study: try a bad string hashing function together with linear hashing and see how bad the performance (expressed as average probes per operation) becomes. It should be easy to change at least the hash function (and keep the same open addressing method). Other requirements GLOBAL VARIABLES are NOT ALLOWED: neither for the hash table, nor for counting probes.