Due Date: Thursday, 14 February
Individual project
Objectives
- Concepts
- data structures, especially hashing
- algorithmic complexity
- Coding tools and conventions
- Eclipse IDE
- Java project organization
- Java coding and documentation standards
- Java language
- Design
- design with inheritance
- design with interfaces
- Strategy pattern
- Testing and evaluation
- Test-driven development
- Unit testing using JUnit
- performance evaluation
Project Description
The starting point for this project is the generic java.util.Map interface. Your job is as follows:- (10%) create a Java project in Eclipse
- (15%) develop a comprehensive JUnit 4 test case for the Map interface
- (5%) using inheritance, create one specialized version of the test case for each of the following implementations:
- java.util.HashMap
- java.util.TreeMap
- java.util.LinkedHashMap
- (40%) based on another specialized version of the test case, develop your own implementation, ChainedHashMap, using a fixed-size hash table with chaining
- (10%) develop a performance evaluation class for the Map interface
- (10%) apply the the performance evaluation to all four implementations (see details below)
- (10%) provide sufficient documentation in the form of inline and Javadoc comments
Additional requirements
- Make sure your project has separate src and test folders and refers to JUnit 4 as a library.
- Implement the Map interface as a hash table with chaining using java.util.LinkedList.
- Ignore the three view methods (entrySet, keySet, and values) in the Map interface for the purpose of this project, including testing. Your implementation should throw a java.lang.UnsupportedOperationException in the body of these methods.
- For each of the remaining 11 interface methods, you need at least two test methods. For example, test isEmpty on an empty and a non-empty map.
- Unlike the existing Java map implementations, your implementation must provide a constructor that allows you to pass the hash function as an argument when an instance your class is created. The constructor should also take the table size as another argument.
- Represent hash functions as objects with the following generic interface:
}
- Implement the following hash functions for integer keys:
- last two digits
- last three digits
- digit sum (e.g. digitSum.apply(1234) returns 10)
- modulo some positive number
- Use System.currentTimeMillis() to calculate running times.
- Measure the performance as follows:
- create another JUnit 4 test case for this purpose
- using the @BeforeClass and @AfterClass annotations, create the following "permanent" fixtures:
- one (long) LinkedList of random keys to insert (partially) into the map
- one (not so long) LinkedList of random keys to query the map for
- write an auxiliary method void doMeasure(String label, Map map, int n, int r) that inserts a specific number, n, of keys (using some dummy value to map to) from the first list, measures the performance for a given large number, r, of retrievals from the second list, and prints the result using the given label
- for each configuration of map implementation, table size (in the case of your implementation), and hash function (in the case of your implementation), write a @Test method that configures the map instance and performs the measurements for the various numbers of insertions
- Specifically, measure the following configurations:
- java.util.HashMap
- java.util.TreeMap
- java.util.LinkedHashMap
- ChainedHashMap, last two digits, size 100
- ChainedHashMap, last three digits, size 1000
- ChainedHashMap, digit sum, size 100
- ChainedHashMap, modulo 101, size 101
- ChainedHashMap, modulo 1009, size 1009
- ChainedHashMap, modulo 10007, size 10007
- ChainedHashMap, modulo 100003, size 100003
- and the following number of insertions:
- 100
- 1000
- 10000
- 100000
- ...
- choose the number of retrievals, r, globally such that your smallest measurements are at least 100 milliseconds
- choose the maximum number of insertions such that the longest running times stay around a minute or below
Submission
- Please refer to the online submission procedure.
