Due Date: Tue 4 Oct (final!)
- Design with interfaces
- Design with inheritance
- Associative data structures
- Strategy pattern
- C# delegates
This project is a continuation of projects 1a and 1b. Your job is as follows.
- Develop your own implementation of the IDictionary interface (not including the extension methods) called ChainedHashMap, which uses a fixed-size hash table with chaining.
- In your implementation, use one of C#'s list implementations and other predefined classes where appropriate. In other words, put together the functionality of the hash table but rely on available building blocks instead of building from scratch.
- Unlike the predefined 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.
- Do not implement the methods Keys, Values, or GetEnumerator (see extra credit below).
- Create the following generic delegate to represent hash functions as objects:
- public delegate int ToInteger<T>(T item);
- Implement the following hash functions for integer keys:
- last two digits
- last three digits
- digit sum (e.g. digitSum(1234) returns 10)
- modulo some positive number
- Using the same suitable reuse and parameterization techniques as in project 1b, create a specialized test suite for this implementation class based on the test suite you created for IDictionary.
- Also apply your performance evaluation test suite from project 1b to this implementation class. This time, measure only retrievals (ContainsKey method). Specifically, for each dictionary size and hash function (in the case of your implementation), write a test method that creates a suitable dictionary instance (parameterized with the given hash function) and performs the measurements for the various numbers of insertions. Do this for the following configurations:
- 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
- Choose the number of repeated retrievals, r, globally such that your smallest measurements are at least 100 milliseconds.
- Choose the maximum load of the table (maximum number of table entries) such that the longest running times stay around a minute or below.
- Interpret your findings and include your answers to the following questions in a write-up of about 300 words:
- How does the choice of table size impact performance?
- How does the choice of hash function impact performance?
- Overall, how does the performance of your implementation compare to the ones included in the .NET framework (Dictionary, SortedDictionary)?
- Be sure to provide sufficient documentation in the form of a readme file, inline comments, and XML doc comments.
- 8 chained hash table implementation/correctness test
- 1 genericity
- 1 parameterization with hash function
- 0.5 points for each of 3 IDictionary properties (i.e., not counting Keys, Values)
- 0.5 points for each of 9 IDictionary methods (i.e., not counting GetEnumerator)
- 1.5 hash function implementations
- 1.5 performance test
- 0.5 Add/Remove
- 1 ContainsKey (in isolation, for globally fixed number of reps, should grow with # items)
- 2 written part
- 0.5 describe results
- 0.5 compare with platform-provided implementations
- 1 interpret results e.g. Dict hash, SortedDict tree
- 2 documentation
Correctly implement the members Keys, Values, and GetEnumerator.