Description: Your objective is to implement your own Dictionary class that uses a hash table as the backing data structure (as explained in the lecture notes). This table will contain an array of KeyValuePair objects (which each contain a key and a value). Your initial table size should be 7 buckets. Specifically you are to do the following: Create a public generic class called Dictionary. This class will contain two generic types, one for the key and one for the value of each KeyValuePair object. Refer to the given KeyValuePair class to see how to do two generic types for a single class. This Dictionary class should have the following: Fields o An array of KeyValuePair objects that we will use as our hash table o A special "deleted" KeyValuePair object to use for marking an entry as being deleted. This can be defined as: private final KeyValuePair DELETED = new KeyValuePair (null, null); Methods insert (key, value) search (key) inserts the specified (key, value) pair into the dictionary (as a KeyValuePair object). If key is already found, value is overwritten searches for the given key in the dictionary and returns the corresponding value if found, null otherwise deletes the (key, value) pair from the dictionary delete(key) You may create other fields and methods if you want, but you must at least have the ones outlined above. For collision handling, you must use linear probing from the notes. For hashing use the following: . The prehash function will be Java's built-in hashCode() function called on the key. The hash function will be the division method from the notes. . is when allocating your hash table. Java has a weird quirk that doesn't allow this unless you allocate it as an array of KeyValuePair objects without the generic parameters and then cast it like so: (KeyValuePair[]) new KeyValuePair[7]; Failure to allocate the array like that will result in an error in Java. This assumes that your dictionary uses the same K and V type parameters as your KeyValuePair class, but of course you can rename those if you like. Note that this will create a warning when you compile your code. The warning will look something like this: Note: ./Dictionary.java uses unchecked or unsafe operations. Note: Recompile with -xlint: unchecked for details. You can safely ignore this warning. I will not take off points for this warning popping up. Entry Point: Create a public class called Main that contains your entry point. The entry point should create an object of your Dictionary class with String as the datatype for its keys and Integer as the datatype for its values. This dictionary will hold the salary of several employees. The keys are names of the employees and the values are the salaries (in increments of 1,000). After declaration and instantiation, insert the following keys and values using the insert function: KEY VALUE Bob Bill 120 Roger 80 Kevin 350 Jerry 65 Liam 500 Now use the search function to find each employee by name and print out their salary (refer to the sample output below). After printing them out, delete the entries for "Bob", "Roger" and Jerry". Also call the insert function with "Liam" as the key and 650 as the value. Remember insert should replace the value in the table if it finds the key is already there. Print out the salaries again and this time, if the search function ever returns null, print out that that employee got fired. You must actually check the results of your search function for null and not just assume Bob, Roger and Jerry were fired. Again refer to the sample output below for clarity. 50 Sample Output: $ javac Main.java && java Main Bob makes $50k a year Bill makes $120k a year Roger makes $80k a year Kevin makes $350k a year Jerry makes $65k a year Liam makes $500k a year Bob got fired Bill makes $120k a year Roger got fired Kevin makes $350k a year Jerry got fired Liam makes $650k a year