Introduction
Part1:
The HashMap class has an initial array size of 13, and uses a threshold of 0.75.
First, we caculate the index for each item according to the hashcode.
index = hashcode % 13
Item Hashcode index
Ellie 1342415373 0
John 700052533 11
Sarah 330628742 2
David 532189483 7
Karen 213142585 6
Ronald 2132979549 12
Tom 207269348 0
Tim 1630149803 9
1):When using separate chaining:
0 1 2 3 4 5 6 7 8 9 10 11 12
Ellie Tom Sarah Karen David Tim John Ronald
2):When using quadratic probing:
0 1 2 3 4 5 6 7 8 9 10 11 12
Ellie Tom Sarah Karen David Tim John Ronald
Requirement
This assignment consists of two parts. The first part does not require coding; however, you could write a program to print the solution. You need to answer the questions and submit a document containing your answers. The second part requires coding. You must submit a Java file containing your solution for this part.
Part 1: 10 Points
For all the questions assume you have a HashMap class that uses a threshold of 0.75 regardless of the collision resolution mechanism used and has an initial array size of 13. Assume the array is resized, when the current item to be added will make the load factor greater than or equal to the threshold value. Recall that the load factor is the fraction of a hash map that is full.
Table 1 contains a list of items, along with associated hash codes that were computed using some hypothetical hash function. Assume the items are added to a newly created instance of the HashMap class in the same order in which they are listed in the table. Based on this information, answer the following questions.
1.(5 points) Show what the array of the HashMap would look like after all the items below have been added, assuming the HashMap class uses separate chaining to resolve collisions.
2.(5 points) Show what the array of the HashMap would look like after all the items below have been added, assuming the HashMap class uses quadratic probing to resolve collisions.
Note that for both questions, you do not need to compute the hashcodes, you only need to determine where the items would be placed into the underlying array of the HashMap.
Table 1 Hashcode pairs for Part 1
Item Hashcode
Ellie 1342415373 0
John 700052533 11
Sarah 330628742 2
David 532189483 7
Karen 213142585 6
Ronald 2132979549 12
Tom 207269348 0
Tim 1630149803 9
Part 2 – 20 pts.
ARP stands for Address Resolution Protocol and is a way for a network to tie a machines MAC address to it’s IP address on a network. IP addresses change and can be applied to any machine, but every machine has a unique MAC address that is tied to it. (If you open up a termina/cmd prompt/powershell in your machine and issue the command arp -a you can get a list of HWADDR or Physical Address (the MAC) and the associated IP address). For part 2, you will be writing an ARP cache program that will receive commands and based on those commands will update the cache.
Input
The input to your program should be a file called arpcmds.txt. In this file, there will be a command followed by input for the command on each line. You can safely assume that the IP and MAC addresses are correctly formatted and that there are no incorrect commands. This file will simulate a pseudo-network. A sample arpcmds.txt file is provided for testing but will not be complete so be sure to write your own tests for edge cases.
The following are the commands followed by their input.
0xa5c IPADDR - This command accepts a single IP address and prints the MAC address. If no IPADDR is found, then print AVAILABLE.
0xa6c MAC - This command accepts a single MAC address and prints the IP address. If no MAC is found then print NO MAC FOUND.
0xb0d MAC IPADDR S/D - This command accepts a MAC, an IP address and a status of S for static or a D for dynamic and stores the information.
oThis associates the MAC to the IP address.
oIf the IP address already exists, do the following depending on the status of the IP address in the cache.
If S, do nothing.
If D, update it.
oTwo MAC addresses cannot share the same IP address so do nothing in this instance.
0x000 IPADDR - This takes an IP address and removes it from the cache. If it is not found, then do nothing.
0x001 MAC - This takes a MAC address and removes it from the cache. If it is not found, then do nothing.
ARP Cache Class
The ARPCache class uses a dictionary type to store the associations of MAC address to IP Address. The methods in this class should resemble the commands used and are wrapper methods for the dictionary methods (whichever type you decide to use). The term wrapper method means a method that calls a second method for the sole purpose of creating an abstraction layer. It can do some additional checks and balances if necessary but for the most part calls a second method that does the real processing. The ARPCache class is just a wrapper class for the dictionary type but only allows access through its methods. In other words, the outside world won’t have access to the underlying dictionary type except through the ARPCache class. This is encapsulation with abstraction.
Additional Classes
You may use additional classes that you write yourself. Any additional classes you write must be submitted along with your ARPCache class and the main class with the main method of your program.
Restrictions
You must utilize a dictionary type to store the information. You do not need to create your own, you may use the built-in library.
HINT: It may be beneficial to use two instances of a dictionary type.
What you need to turn in
You must submit your ARPCache class, the main class that contains the main method, and any additional classes you may have used to help you. The best way to submit is to zip your entire project folder and submit your zip file.
This problem set is straight forward and open for implementation with only one restriction which is the use of a dictionary type. Either the code works, or it doesn’t so no rubric is given.