Java/Python编程设计讲解、辅导data留学生程序

日期：2021-04-11 10:38

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).