public class HashMap {
  HashEntry[] table;
  float loadFactor;
  int numItems;

  public HashMap() {
    init(16, 0.75f);
  }

  public HashMap(int initialCapacity) {
    init(initialCapacity, 0.75f);
  }

  public HashMap(int initialCapacity, float loadFactor) {
    init(initialCapacity, loadFactor);
  }

  private void init(int initialCapacity, float loadFactor) {
    table=new HashEntry[initialCapacity];
    this.loadFactor=loadFactor;
    this.numItems=0;
  }

  private static int hash(Object o, int length) {
    if (o==null)
      return 0;
    int value=o.hashCode()%length;
    if (value<0)
      return -value;
    return value;
  }

  void resize() {
    int newCapacity=2*table.length+1;
    HashEntry[] oldtable=table;
    this.table=new HashEntry[newCapacity];

    for(int i=0; i<oldtable.length; i++) {
      HashEntry e=oldtable[i];
      while(e!=null) {
	HashEntry next=e.next;
	int bin=hash(e.key, newCapacity);
	e.next=table[bin];
	table[bin]=e;
	e=next;
      }
    }
  }

  public boolean isEmpty() {
    return numItems==0;
  }

  public int size() {
    return numItems;
  }

  /* 0=keys, 1=values */
  public HashMapIterator iterator(int type) {
    return new HashMapIterator(this, type);
  }

  Object remove(Object key) {
    int bin=hash(key, table.length);
    HashEntry ptr=table[bin];
    if (ptr!=null) {
      if (ptr.key.equals(key)) {
	table[bin]=ptr.next;
	numItems--;
	return ptr.value;
      }
      while(ptr.next!=null) {
	if (ptr.next.key.equals(key)) {
	  Object oldvalue=ptr.value;
	  ptr.next=ptr.next.next;
	  numItems--;
	  return oldvalue;
	}
	ptr=ptr.next;
      }
    }
    return null;
  }

  Object get(Object key) {
    int bin=hash(key, table.length);
    HashEntry ptr=table[bin];
    while(ptr!=null) {
      if (ptr.key.equals(key)) {
	return ptr.value;
      }
      ptr=ptr.next;
    }
    return null;
  }

  boolean containsKey(Object key) {
    int bin=hash(key, table.length);
    HashEntry ptr=table[bin];
    while(ptr!=null) {
      if (ptr.key.equals(key)) {
	return true;
      }
      ptr=ptr.next;
    }
    return false;
  }

  Object put(Object key, Object value) {
    numItems++;
    if (numItems>(loadFactor*table.length)) {
      //Resize the table
      resize();
    }
    int bin=hash(key, table.length);
    HashEntry ptr=table[bin];
    while(ptr!=null) {
      if (ptr.key.equals(key)) {
	Object oldvalue=ptr.value;
	ptr.value=value;
	return oldvalue;
      }
      ptr=ptr.next;
    }
    HashEntry he=new HashEntry();
    he.value=value;
    he.key=key;
    he.next=table[bin];
    table[bin]=he;
    return null;
  }
}