Due Date: Tue 4 Oct (final!)
Design with interfaces
Design with inheritance
Associative data structures
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 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
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