Lab: Hashing

Beware of the dreaded HashMonster!


Download hashinglab.zip. In this lab, you will implement an efficient set using hashing.

Implement parts 1 and 2 to earn 90%.
Implement parts 1, 2, and 3 to earn 95%.
Earn additional credit by completing the more challenging exercises listed at the bottom of the page.


Part 1:  Product

The Product class has been provided to you. It represents a product you might purchase, with a model name and a version number. For example:

Product p = new Product("iphone", 11);
String model = p.getModel(); //returns "iphone"
int version = p.getVersion(); //returns 11


Complete the Product class's hashCode method, so that it is both valid (equivalent Products return the same value) and good (unequal Products usually return different values).


Part 2:  MyHashSet

The MyHashSet class represents a kind of set. Like all sets, MyHashSet cannot have any duplicate elements. Inside a MyHashSet, values are stored in a hash table using two fields:

private ListNode<E>[] buckets; // an array of buckets, where each bucket is a linked list

private int size;              // the number of elements in the set

In this part, you must implement 3 methods in MyHashSet, which you should complete in this order:


Part 3:  remove

Implement MyHashSet's remove method:
public boolean remove(Object obj)
This method removes obj from the set and returns true if successful. It returns false if obj was not present in the set. It must run in expected O(1) time and worst-case O(n) time.

Additional Credit Suggestions


Challenge #1
Implement a class called SetIterator, which behaves as follows:
MyHashSet<Integer> set = new MyHashSet<Integer>(5);
set.add(2);
set.add(3);
set.add(7);
SetIterator<Integer> it = set.iterator();
int n;
n = it.next();
n = it.next(); // these lines return 2 and 7, in any order
boolean b;
b = it.hasNext(); // returns true
n = it.next(); // returns 3
b = it.hasNext(); // returns false
n = set.size(); // returns 3 (set hasn't changed)

Neither the iterator method nor the SetIterator class may ever move the elements of the MyHashSet into any other data structure. The total time to loop over the first n elements of MyHashSet using a SetIterator must be O(n + b), where b is the number of buckets.


Challenge #2
Implement MyHashMap<K,V>, with the following methods:
public int size()             // must run in O(1) time
public V get(K key)           // must run in expected O(1) time and worst-case O(n) time
public V put(K key, V value)  // must run in expected O(1) time and worst-case O(n) time