Project 1

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
  
• Object as superclass
• Java annotations
• Java exception handling
• Java generics
• Java collections
• 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:

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
  

Submission

• Please refer to the online submission procedure.