/** 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<B.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<N; 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 ...