Assignment

Description

Implement a class in Java named SeparateChainingHashMap containing the following methods. In our maps, we will store words made up of uppercase and lowercase English letters only. Consider the word string s₀s₁ s_m-1 of length m, then its key will be the sum of ASCII values of its letters and its final hash value (the array index where it will be stored) is given by the function: h(k) = k mod N where N is the size of the hash table and k is the key. We will use separate chaining to handle collisions.

The nodes of the linked lists must have two separate fields - one for the key (integer) and one for the word (String). You should not use the linked list class already defined in the Java library.

1. public SeparateChainingHashMap(int N);

This constructor creates a new empty array of size N for the corresponding singly linked lists to be created after adding words to the map.

2. public int calculateKey(String word); This method returns the key of a word, not necessarily present in the map.

3. public void add(String word);

Adds a new word into the map by calculating its key and finally its hash value. Do not sort the nodes of a linked list. Simply, insert them at the end as they arrive else you may get different output.

4. public boolean remove(String word);

This method removes the word, if it is present in the map. If present, return true else return false.

5. public String remove(Integer key);

This method deletes and returns the word associated with key value key. If such an entry exists, return the word associated with the key else return null.

6. public String toString();

This method returns a human readable string representation of the hash table. To under¬stand this assume that N = 10 and a map contains three words Apple, Cat, Boy with keys 498, 280, 298 (think why?), respectively. Then System.out.println(myHashMap); where myHashMap refers to the hash map object, should print out the following:

9 (289,Cat)
1
2
3
4
5
6
7
8 (498,Apple) -> (298,Boy)
9

Unless stated, in the programs of this course you are not allowed to use any existing Java library and/or external packages for solving the problem. You should write everything from the scratch. You will receive zero i fyour program does not compile or it is found that you have copied code from some other source without any reference.

Deliverable

Upload the file SeparateChainingHashMap. java only. You are not allowed to submit any other file. Your java code should be properly indented and nicely commented. Feel free to use additional helper methods, if required.

Attachment:- Separate-Chaining-Hash-Map.java-Partial-Code.rar