public class HashTable implements Map {
	protected static class HashEntry implements Entry {
	Object key, value;
	HashEntry () { /* default constructor */ }
	HashEntry(Object k, Object v) { key = k; value = v; }
	public Object key() { return key; }
	public Object value() { return value; }
	protected Object setValue(Object v) { // set a new value, returning old
	Object temp = value;
	value = v;
	return temp; // return old value
	}
}
/** Nested class for a default equality tester */
protected static class DefaultEqualityTester implements EqualityTester {
	DefaultEqualityTester() { /* default constructor */ }

/** Returns whether the two objects are equal. */
public boolean isEqualTo(Object a, Object b) { return a.equals(b); }
	}
	protected static Entry AVAILABLE = new HashEntry(null, null); // empty
	marker
	protected int n = 0; // number of entries in the dictionary
	protected int N; // capacity of the bucket array
	protected Entry[] A; // bucket array
	protected EqualityTester T; // the equality tester
	protected int scale, shift; // the shift and scaling factors

/** Creates a hash table with initial capacity 1023. */
public HashTable() {
	N = 1023; // default capacity
	A = new Entry[N];
	T = new DefaultEqualityTester(); // use the default equality tester
	java.util.Random rand = new java.util.Random();
	scale = rand.nextInt(N-1) + 1;
	shift = rand.nextInt(N);
}

/** Creates a hash table with the given capacity and equality tester. */
public HashTable(int bN, EqualityTester tester) {
N = bN;
A = new Entry[N];
T = tester;
java.util.Random rand = new java.util.Random();
scale = rand.nextInt(N-1) + 1;
shift = rand.nextInt(N);
}



/** Determines whether a key is valid. */
protected void checkKey(Object k) {
	if (k == null) throw new InvalidKeyException("Invalid key: null.");
}

/** Hash function applying MAD method to default hash code. */
public int hashValue(Object key) {
	return Math.abs(key.hashCode()*scale + shift) % N;
}

/** Returns the number of entries in the hash table. */
public int size() { return n; }

/** Returns whether or not the table is empty. */
public boolean isEmpty() { return (n == 0); }

/** Helper search method - returns index of found key or -index-1,
* where index is the index of an empty or available slot. */
protected int findEntry(Object key) throws InvalidKeyException {
	int avail = 0;
	checkKey(key);
	int i = hashValue(key);
	int j = i;
	do {
	if (A[i] == null) return -i - 1; // entry is not found
	if (A[i] == AVAILABLE) { // bucket is deactivated
		avail = i; // remember that this slot is available
		i = (i + 1) % N; // keep looking
	}
	else if (T.isEqualTo(key,A[i].key())) // we have found our entry
		return i;
	else // this slot is occupied--we must keep looking
		i = (i + 1) % N;
	} while (i != j);
	return -avail - 1; // entry is not found
}

/** Returns the value associated with a key. */
public Object get (Object key) throws InvalidKeyException {
	int i = findEntry(key); // helper method for finding a key
	if (i < 0) return null; // there is no value for this key
	return A[i].value(); // return the found value in this case
}


/** Put a key-value pair in the map, replacing previous one if it exists. */
public Object put (Object key, Object value) throws InvalidKeyException {
	if (n >= N/2) rehash(); // rehash to keep the load factor <= 0.5
	int i = findEntry(key); //find the appropriate spot for this entry
	if (i < 0) { // this key does not already have a value
	A[-i-1] = new HashEntry(key, value); // convert to the proper index
	n++;
	return null; // there was no previous value
	}
	else // this key has a previous value
	return ((HashEntry) A[i]).setValue(value); // set new value & return old
}

/** Doubles the size of the hash table and rehashes all the entries. */
protected void rehash() {
	N = 2*N;
	Entry[] B = A;
	A = new Entry[N]; // allocate a new version of A twice as big as before
	java.util.Random rand = new java.util.Random();
	scale = rand.nextInt(N-1) + 1; // new hash scaling factor
	shift = rand.nextInt(N); // new hash shifting factor
	for (int i=0; i&ltB.length; i++)
	if ((B[i] != null) && (B[i] != AVAILABLE)) { // if we have a valid entry
	int j = findEntry(B[i].key()); // find the appropriate spot
	A[-j-1] = B[i]; // copy into the new array
}
}

/** Removes the key-value pair with a
specified key. */
public Object remove (Object key) throws InvalidKeyException {
	int i = findEntry(key); // find this key first
	if (i < 0) return null; // nothing to remove
	Object toReturn = A[i].value();
	A[i] = AVAILABLE; // mark this slot as
	deactivated
	n--;
	return toReturn;
}

/** Returns an iterator of keys. */
public java.util.Iterator keys() {
	List keys = new NodeList();
	for (int i=0; i&ltN; i++)
	if ((A[i] != null) && (A[i] != AVAILABLE))
	keys.insertLast(A[i].key());
	return keys.elements();
	}
} // ... values() is similar to keys() and is omitted here ...