In the last lab you created array and linked implementations of a list. The list interface did not define a find operation because it does not make sense to search for an object you already have. This is not the case, however, with a map. A map is a class that stores values, like a list, but the values are accessed by key instead of index. A common example of a use for a map is a dictionary. Words in the dictionary are the keys and the definitions are the values. In this lab you are going to create both an array and a list implementation of a map and compare their performance.
The file Map.java contains an interface that defines all of the methods for map classes. Look at the file and read through the comments for the methods to make sure that you understand all of them. Notice that the interface defines two generic types, K and V, for the keys and values. For this lab you should create a two classes, ArrayMap and LinkedMap, that implement the Map interface using an array or linked implementation. Feel free to use your code from the last lab to help write these classes. If you would prefer you can use the code in the file LinkedList.java. Note that because a map does not allow index access to elements it is not necessary to keep elements in order when removing an object.
Remember to code in small pieces and test thoroughly. Proceed only when you are sure that your classes are functioning properly. Which implementation do you think performs more quickly? The file GraphMapTime.java contains a program that will plot the time it takes to complete various operations on array and linked implementations of maps. Run this program to verify if your conclusions about the performance of these implementations are correct.
It is possible to speed up the performance of the get operation of the map if binary search is used instead of linear search. In order to implement binary search, however, the elements must be in sorted order. It does not make sense to sort the elements before performing a binary search. Why not? So, the add method should be modified to add elements in sorted order. Create a class SortedArrayMap, that implements the Map interface using an array where the elements are stored in the order of their key values. Why does it not make sense to implement a SortedLinkedMap? The class can extend ArrayMap so that the constructor, toString, and remove methods do not need to be rewritten.
Again, remember to code in small pieces and test thoroughly. Proceed only when you are sure that your class is functioning properly. Which implementation do you think performs more quickly? The file GraphSortedMapTime.java contains a program that will plot the time it takes to complete various operations on array and linked implementations of maps. Run this program to verify if your conclusions about the performance of these implementations are correct.
To submit your code: Tar the files in your lab9 directory and copy the tgz file to the directory /home/staff/bouchard/CPSC170A/lab9. Be sure to name the tar file with your names, not lab9.tgz.