Sunday, January 27, 2008

Project 1

Due Date: Thursday, 14 February

Individual project


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:
interface ToInteger<T> {
int apply(T arg);
  • 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


No comments: