3.8 Hash Set

Requirements

Create an implementation of Java's Set interface called LinearProbingHashSet that utilizes linear probing. You implementation should start with an initial array (I highly recommend that you use ArrayList instead of an actual array) of size 10 and should double the size whenever the array is more than halfway full.

You may not use Java's built-in HashSet class or HashMap class. However, you are welcome to use other Java collections.

In the interest of not making this assignment too difficult, you will not be required to implement remove(Object), removeAll(Collection), or retainAll(Collection). You may, however, implement remove(Object) for extra credit if you choose.

Hints

Use an ArrayList instead of an actual array inside your class to store your hash table. To indicate an empty index in the array, just insert null.

Testing

Some of the unit tests perform simple checks such as verifying that an item can be found in the set after it is added. However, those tests can only verify that you have correctly implemented the set interface but cannot check that you are correctly using linear probing or that you are correctly doubling your size whenever it is more than halfway full. In order to test these requirements, some of the test code will check how many times .equals() and .hashCode() are called on the contained items. Because of this, you will need to make sure that you aren't ever calling either of these methods more times than they are needed.

Extra Credit

For extra credit, correctly implement the remove(Object) method.

In linear probing, you need to keep track of which indexes in your array are empty because nothing was ever added, and which indexes are empty because the item was removed. The easiest way to do this is to just have an ArrayList since you no longer need to keep track of items that were removed prior to the grow operation.

Submission File: LinearProbingHashSet.java

Test driver will be provided if needed.