In this assignment, you implement a hash table using chained hashing. The hash table size is determined at initialization time and never changes. Each hash table entry is a linked list, so each hash table entry can hold any number of values. You may use a linked list from the Java API, or one from one of your previous assignments.
Your hash table must be designed to map keys to values. None of the keys or values are allowed to be null. Keys are compared using the .equals method.
Your hash table should use the hashCode() method to compute the hash for a given string. Use Math.abs to turn that into a positive value, and modulo to make it into an array index (this description is not quite enough, so you will have to figure out exactly how to make this work).
Your hash table class (called Hash211<K,V>) must provide the following methods:
Hash211<K,V>(int capacity, boolean printTimes); // constructor
V put(K key, V value); // add or replace a Key,Value
V get(K key); // return a value for the given key
Each of these functions is described in more detail here and here.
You should analyze and measure the runtime of your hash table put and get operations in two cases:
When the hash table size s is much larger (at least 10 times larger) than the number n of elements added.
When the hash table size s is much less (at least 10 times less) than the number n of elements added. Your analysis should match your measured results. Write up your analysis and make enough measurements to be clear and convincing.
This part of the assignment is worth 20% of the grade.
Anthony Christe has provided a test program, HashTableStressTest.java, to make it easy for you to add a large number of strings to your hash table.
It’s a command line program that takes two arguments and an optional third argument.
java HashTableStressTest dictionary_file capacity [-pt --print-times]
where dictionary_file is the location of the dictionary file which is a text file with a single word per line, and capacity is the initial capacity of the hashtable.
The final option will pass either true or false to printTimes in the Hash211 constructor. If it is not specified then printTimes will be false. If the option is specified, then the times will be printed.
Anthony has also provided two dictionary files, dict.txt (234,937 words) and dict-small.txt (99,171 words).
You must also build your own test code to make sure that your implementation works. Turn in your test code together with the Hash211 class and your analysis.
Please thoroughly test your code and briefly discuss your testing strategy. Turn in all test code.
The assignment is due on Friday at 11:59pm. You may turn it in early. If you haven’t completed the assignment by 11:58, turn in what you have. Getting partial credit is much better then no credit.