JAVA

HASH SET

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.

You may find the hash set that we implemented in class to be a useful example (code is posted on canvas). However, you should remember that the example class used chaining instead of linear probing. The ArrayList> that we used in the chaining example will just be an ArrayList in the linear probing example.

Our discussion of linear probing in class was very brief, however, you should be able to understand it by looking through the lecture slides (posted on canvas).

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. If you fail a test based on the number of times one of these methods is called and you feel that you have good justification for your implementation, please email me.

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.