Use hash tables, a common data structure, to implement a programming problem Implement a spelling checker by using a hash table. Start by reading the starter code. Use the following steps: Your code...

• 
  
  Use hash tables, a common data structure, to implement a programming problem
  
  
  
  
  

Implement a spelling checker by using a hash table. Start by reading the starter code.

Use the following steps:

1. Your code should import this code from the textbook:https://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/SeparateChainingHashST.java.htm(Links to an external site.)land use it as a library. Do not change this code.


2. Downloadthis starter code(https://cdn.inst-fs-iad-prod.inscloudgate.net/d6668aae-e21e-4d7f-99a2-086a149f3183/SpellChecker.java?token=eyJhbGciOiJIUzUxMiIsInR5cCI6IkpXVCIsImtpZCI6ImNkbiJ9.eyJyZXNvdXJjZSI6Ii9kNjY2OGFhZS1lMjFlLTRkN2YtOTlhMi0wODZhMTQ5ZjMxODMvU3BlbGxDaGVja2VyLmphdmEiLCJ0ZW5hbnQiOiJjYW52YXMiLCJ1c2VyX2lkIjoiOTk1NDAwMDAwMDAwNjA5MzMiLCJpYXQiOjE2Mzg5MDg5MjQsImV4cCI6MTYzODk5NTMyNH0.OJlNTVbs788CdMCmrwUPctkjdHJZNqlTF3OdcWDAXYl_QrGj9K2pmEVNq_87Ov9mPEwSp_7ZkNMnEI_w_70P_g&content_type=text%2Fx-java)and thewords.txt(https://cdn.inst-fs-iad-prod.inscloudgate.net/c72e42e0-be89-44bb-99af-073a1fe81b9c/words.txt?token=eyJhbGciOiJIUzUxMiIsInR5cCI6IkpXVCIsImtpZCI6ImNkbiJ9.eyJyZXNvdXJjZSI6Ii9jNzJlNDJlMC1iZTg5LTQ0YmItOTlhZi0wNzNhMWZlODFiOWMvd29yZHMudHh0IiwidGVuYW50IjoiY2FudmFzIiwidXNlcl9pZCI6Ijk5NTQwMDAwMDAwMDYwOTMzIiwiaWF0IjoxNjM4OTI0ODI2LCJleHAiOjE2MzkwMTEyMjZ9.TN3EMaHfKm5zMGJgQNQFW00Kp1HXV1UElEw43IE3vJWLo1HtyXHBd8KPBZXwvLsi_TZldu5MquKs94lYiCO8KQ&content_type=text%2Fplain) file


3. In the initDictionary() method in the starter code, write new code that reads a file of words and creates a hash table of correctly spelled words.


4. Write code in main() that repeatedly prompts the user to type a word and checks each word for spelling mistakes.




• If the word is spelled correctly (found in your hash table), it should print "no mistakes found".


• If the word is not found, it should listallwords that are obtainable by applying any of the following rules exactly once:




1. Add one character to the beginning


2. Add one character to the end


3. Remove one character from the beginning


4. Remove one character from the end


5. Exchange two adjacent characters

There are two ways to implement part 3:

• Given an input word inputWord, loop over all words in the hash table (using the keys() method) and for each word dictionaryWord, check if you can go from inputWord to dictionaryWord using one of the five transformations.


• Given a word inputWord, generate a list stringList of all possible strings you can make by applying one of the five rules. Then, for each string s in stringList, look up s in the dictionary.

Pick which way you think is better for this problem (in terms of number of comparisons). Implement it, and explain why you think it's better.

Examples (add your own too):

• compare the performance of SeparateChainingHashST and LinearProbingHashST


• add code to measure the number of hash collisions when adding words into the table. at the end, what is the average length of a chain? how long is the longest chain? (To do this, you do have to edit the textbook code.)