solve below questions. There are two coding should be created.

1.ExternalChainingMapEntry.java

2.ExternalChainingHashMap.java

HashMap

Forthisassignment, you will be coding anExternalChainingHashMap, a key-value HashMap with an external chaining collision resolution strategy. AHashMapmaps unique keys to values and allowsO(1)average case lookup of a value when the key is known. The table should not contain duplicate keys, but can contain duplicate values. In the event of trying to add a duplicate key, replace the value in the existing (key, value) pair with the new value and return the old value.

IMPORTANT:

• You will begiven 5 attempts on this assignment, with a30 minutecooldownbetween submissions.
• Please run your code before each submission to ensure that there are no formatting errors! If there are formatting errors in your code, your code will not be graded and a submission attempt will be logged. For more information, please review the Vocareum overview below.

Capacity

The starting capacity of the ExternalChainingHashMap using the default constructor should be the constantINITIAL_CAPACITYdefined inExternalChainingHashMap.java. Reference the constant as-is. Donotsimply copy the value of the constant. Donotchange the constant. Donotregrow the backing array when removing elements.

If adding to the table would cause the load factor (LF) toexceed(i.e. greater than, not greater than or equal to) the max load factor constant provided in the java file, the table should be resized to have a capacity of2n + 1, wherenis the current capacity before adding the parameterized element. See the javadocs for specific instructions on when to resize. There is a method calledresizeBackingTablethat you should use for resizing.

Hash and Compression Functions

You should not writeyour own hash functions forthisassignment. Instead, use thehashCode()method that every Object has. For the compression function, mod by table length first, then take the absolute value (it must be done in this order to prevent overflow in certain cases). As a reminder, you should be using thehashCode()method ononly the keys(and not theExternalChainingMapEntryobject itself) since that is what is used to look up the values. After converting a key to an integer with a hash function, the integer must be compressed to fit in the array backing the HashMap.

Adding

When adding a key/value pair to a HashMap, add the pair to the front of the chain in the correct position. Also remember that keys are unique in a HashMap, so you must ensure that duplicate keys are not added. Each index of the table should point to anExternalChainingMapEntrythat represents the head of a linked list. That linked list contains all elements that collide at that index.

Removing

When removing a key/value pair from aHashMap using external chaining, you can safely remove the item. Removing from a chain is very similar to removing from a Singly-Linked List, treating the first tableentry as the head, so refer to your notes and homework assignments from earlier in the course if you need a refresher. As usual, if the entry you are removing is the only entry at that index, you should make sure to null out that spot rather than leaving it there.

Transcribed Image Text:

HashMap (External Chaining) Examples For each example, we assume the hashed index to be abs(key % table.length). Initial HashMap put(5,5) // If the hashed index is empty, we simply place the new (key, value) pair at that index. Initial HashMap (5,5) (6, 6) (19, 19) (32, 32) put(32, 32) // If there are already element(s) at the hashed index, the new (key, value) pair becomes the head of the chain at that index. (8,8) (11, 11) (25, 25) (6, 6) (8,8) (19, 19) (11, 11) (25, 25) HashMap (External Chaining) Examples For each example, we assume the hashed index to be abs(key % table.length). Initial HashMap put(5,5) // If the hashed index is empty, we simply place the new (key, value) pair at that index. Initial HashMap (5,5) (6, 6) (19, 19) (32, 32) put(32, 32) // If there are already element(s) at the hashed index, the new (key, value) pair becomes the head of the chain at that index. (8,8) (11, 11) (25, 25) (6, 6) (8,8) (19, 19) (11, 11) (25, 25)

Answer rating: 100% (QA)

Below are the Java classes for ExternalChainingMapEntry and ExternalChainingHashMap based on the provided specifications 1 ExternalChainingMapEntryjav... View the full answer