Lab Assignment #6 – Using Maps and Hash Tables
Due Date: Friday, Week 11
Purpose: The purpose of this Lab assignment is to:
Design algorithms that describe operations on ADT Maps
Investigate the efficiency of hash table implementations
Implement and test appropriate methods in Java or Python
References: Read the course’s text chapter 10 and the lecture slides. This material provides the necessary information that you need to complete the exercises.
Be sure to read the following general instructions carefully:
- This assignment must be completed individually by all the students.
- You will have to demonstrate your solution in a scheduled lab session and upload the solution on eCentennial through the assignment link.
Exercise 1
Our AbstractHashMap class maintains a load factor l ≤ 0.5. Reimplement that class to allow the user to specify the maximum load, and adjust the concrete subclasses accordingly.
Perform experiments on our ChainHashMap and ProbeHashMap classes to measure its efficiency using random key sets and varying limits on the load factor.
Hint The load factor can be controlled from within the abstract class, but there must be means for setting the parameter (either through the constructor, or a new method).
Write a Java/Python application to test your solution.(7 marks)
Exercise 2
The use of null values in a map is problematic, as there is then no way to differentiate whether a null value returned by the call get(k) represents the legitimate value of an entry (k, null), or designates that key k was not found. The java.util.Map interface includes a boolean method, containsKey(k), that resolves any such ambiguity.
Implement the containKey(k) method for the SortedTableMap class. Hint: Use the existing findIndex(k) method.
Write a Java/Python application to test your solution.
(3 marks)
Evaluation:
Correct implementation of requirements:
Correct ADT data structure algorithm
Correct Java or Python implementation
Explanation of algorithm when asked 90%
Friendly I/O
10%
Total 100%
You must name your Eclipse project according to the following rule:
YourFullname_COMP254Labnumber_Exercisenumber.
Example: JohnSmith_ COMP254Lab6_Ex1
Submission rules:
Submit your modules as zip files that are named according to the following rule:
YourFullname_ COMP254Labnumber_Exercisenumber.zip
Example: JohnSmith_ COMP254Lab6_Ex1.zip
Use 7-zip to compress files (https://www.7-zip.org/download.html).