Write some Software

need by march 25, 5 pm Eastern time US you are to create a class that implements a dictionary (associative array, hash table), that associates Strings with doubles. It should deal with collisions by chaining (using linked lists). Begin by creating the ListElements for the linked lists. These must NOT be templated, since Java forbids arrays of templated objects. It will need a String named "key", a double named "value" and a link. This could, and probably should be an inner class of: a linked list class. It (HashLinkedList) needs ListElement named head, a method to add an element to the list, a method to remove a specified element from the list, a method to return the value associated with a given key within the list, and a method to replace the value associated with a given key to a different value. Finally you will build a Dictionary class which contains an array of LinkedLists. It will be convenient to have a memory cell to hold the size of this array. You will want a constructor which allows the user to specify the hash table size (the size of the array mentioned above), and another constructor that defaults the array size to, say, 100. You will want a method "insert" to insert a key/value into the hash table, and a method "lookup" which returns the value associated with the given key if that key exists in the table. If you insert a key/value pair and the key value already exists, replace its value field with the new value. If you attempt to lookup a value whose key does not exist, throw a KeyNotPresentException (which you will have to write.) Finally, you need a private hash function which I shall discuss at the very bottom of this document. Skeletons of the various classes. Feel free to add other attributes and methods if you find it convenient to do so: public class HashLinkedList { private ListElement head; public HashLinkedList() private static int hash(String) public void insert(String key, double value); public double lookup(String key) throws KeyNotPresentException // remove the entry with the specified key public void delete(String key) // change the value associated with the key public void changeValue(String key) class ListElement //inner class { private String key; private double value; private ListElement link; public ListElement(String key, double value, ListElement link) public ListElement(String key, double value) // defaults link to null public String getKey() public double getValue() public void setValue(double value) // Never any need to change the key } } public class Dictionary { HashLinkedList hashTable[]; private int tablesize; public Dictionary(int size) //use a default table size; public Dictionary() public void define(String key, double value) //lookup key, if not present, add key/value pair, // otherwise change value public void lookup(String key) public void undefine(String key) private static int hash(String key) } How to hash a String: Normally I don't encourage anybody to write their own hash function. Getting it right is too hard. But for this exercise, I want you to have the experience. Use .charAt to retrieve each character in the string, something like a loop continging char c = [login to view URL](i); //bit by bit and to set all but the least signifiant 8 bits to 0. //(ask me about this in class) int i = (int)c & 0xFF; sum = sum + i; After the loop, when all the characters have been processed sum = sum % tableSize; return sum