<![CDATA[
// Roy McElmurry handout #35
// 6/1/11
//
// A simplistic generic HashSet with chaining for collision resolution
// A HashSet provides add(), remove() and contains() operations
// that run in O(1).
import java.util.*;
public class HashSet<E> {
private static final double LOAD_FACTOR = 0.75;
private List<E>[] entries;
private int size;
// Pre: capacity > 0
// Post: creates a HashSet with a hash table of "capacity" size
@SuppressWarnings("unchecked")
public HashSet(int capacity) {
entries = (List<E>[]) (new LinkedList[(int) (capacity / LOAD_FACTOR)]);
}
// Pre: value != null
// Post: Adds the given value to the hash table
public void add(E value) {
if (!contains(value)) {
int i = indexOf(value);
List<E> chain = entries[i];
if (chain == null)
chain = new LinkedList<E>();
chain.add(0, value);
size++;
}
}
// Pre: value != null
// Post: returns whether the hash table contains the given value
public boolean contains(E value) {
int i = indexOf(value);
List<E> chain = entries[i];
return chain != null && chain.contains(value);
}
// Pre: value != null
// Post: removes the given value from the hash table
public void remove(E value) {
if (contains(value)) {
int i = indexOf(value);
List<E> chain = entries[i];
chain.remove(value);
size--;
}
}
// Post: returns the number of elements in the HashSet
public int size() {
return size;
}
// Pre: value != null
// Post: returns the index where the given value should
// be placed in the hash table
private int indexOf(E value) {
return Math.abs(value.hashCode() % entries.length);
}
}
]]>