HashMap.java

Go to the documentation of this file.

package aud;
 
import java.util.Iterator;
 
public class HashMap<Key,Value> {
 
  // TODO define ADT AbstractUnorderedMap (extends AbstractMap)
  // TODO define unit test for HashMap
 
  // primes stolen from an older version of gcc's STL
  static final int PRIMES[]={
    31,        53,         97,         193,       389,
    769,       1543,       3079,       6151,      12289,
    24593,     49157,      98317,      196613,    393241,
    786433,    1572869,    3145739,    6291469,   12582917,
    25165843,  50331653,   100663319,  201326611, 402653189,
    805306457, 1610612741
  };
  static int getNextPrime(int n) {
    for (int p : PRIMES)
      if (p>=n)
        return p;
    throw new RuntimeException("table size exceeds limits"); // unrealistic!
  }
 
  class Bucket {
    Bucket(Key key,Value value) {
      this.key=key;
      this.value=value;
    }
    Key    key;
    Value  value;
    Bucket next=null;
  };
 
  public class Entry {
    Entry(Key key,Value value) {
      this.key=key;
      this.value=value;
    }
    public Key    key;
    public Value  value;
  }
 
  public class Entries implements Iterable<Entry> {
    HashMap<Key,Value> hashmap_;
    Entries(HashMap<Key,Value> hashmap) { hashmap_=hashmap; }
    @Override public Iterator<Entry> iterator() {
      return new EntryIterator(hashmap_);
    }
  }
 
  class EntryIterator implements Iterator<Entry> {
    HashMap<Key,Value> hashmap_;
    int                idx_;
    Bucket             bucket_=null;
 
    @SuppressWarnings("unchecked")
    EntryIterator(HashMap<Key,Value> hashmap) {
      hashmap_=hashmap;
      // find first entry
      for (idx_=0;idx_<hashmap_.table_.length;++idx_) {
        if ((bucket_=(Bucket) hashmap_.table_[idx_])!=null)
          break;
      }
    }
 
    @SuppressWarnings("unchecked") void advance() {
      assert(bucket_!=null);
      bucket_=bucket_.next; // we may reach the end of the list
 
      while (bucket_==null) {
        if (++idx_>=hashmap_.table_.length)
          break;
        bucket_=(Bucket) hashmap_.table_[idx_];
      }
    }
 
    @Override public boolean hasNext() {
      return bucket_!=null;
    }
 
    @Override public Entry next() {
      assert(bucket_!=null);
      Entry entry=new Entry(bucket_.key,bucket_.value);
      advance();
      return entry;
    }
 
    @Override public void remove() {
      throw new UnsupportedOperationException();
    }
  }
 
 
  Object  table_[] = null;  // stores Bucket instances (Java generics suck!)
  double  maxLoad_ = 0.75;
  int     size_    = 0;
 
  public HashMap(int size) {
    int n=(int) ((double) size/maxLoad_);
    if (n<size) n=size;
    n=getNextPrime(n);
    table_=new Object[n];
  }
 
  public HashMap() {
    this(PRIMES[0]);
  }
 
  public int getHashtableSize() {
    return table_.length;
  }
 
  public int size() { return size_; }
 
  public boolean is_empty() { return size_==0; }
 
  public double getLoadFactor() {
    return (double) size_/(double) table_.length;
  }
 
  void setMaximumLoadFactor(double alpha) {
    if (alpha<maxLoad_ && getLoadFactor()>alpha)
      rehash(alpha);
 
    maxLoad_=alpha;
  }
 
  public void reserve(int size) {
    if (size>size_)
      rehash((int) ((double) size)/maxLoad_);
  }
 
  void rehash(double alpha) {
    rehash((int) (alpha* (double) size_));
  }
 
  @SuppressWarnings("unchecked")
  void rehash(int newSize) {
    int n=getNextPrime(newSize);
    System.err.println("INFO: rehash "+table_.length+" -> "+n+
        " ("+size_+" entries, load factor "+getLoadFactor()+")");
    HashMap<Key,Value> ht=new HashMap<Key,Value>(n);
    for (Object position : table_) {
      for (Bucket b=(Bucket) position;b!=null;b=b.next) {
        ht._set(b.key,b.value);
      }
    }
    // steal data from ht
    table_=ht.table_;
    size_=ht.size_;
  }
 
  public Entries entries() { return new Entries(this); }
 
  @SuppressWarnings("unchecked")
  Value _set(Key key,Value value) {
    int hash = key.hashCode();
    hash = hash < 0 ? -hash : hash;
    int i=hash % table_.length;
    if (table_[i]==null) {
      if (value!=null)                 // (key,null) is never stored
        table_[i]=new Bucket(key,value);
    }
    else {                             // collision
      Bucket tail=null;
      for (Bucket b=(Bucket) table_[i];b!=null;b=b.next) {
        if (b.key.equals(key)) {       // Is key already in list?
          Value old=b.value;
          b.value=value;               // YES: change
 
          if (value==null) {           // special case: remove
            if (tail==null)
              table_[i]=b.next;
            else
              tail.next=b.next;
            --size_;
          }
 
          return old;
        }
        tail=b;
      }
      assert(tail!=null);
      tail.next=new Bucket(key,value); // NO: insert at end of list
    }
    ++size_;
 
    return null;
  }
 
  public Value insert(Key key,Value value) {
    Value v=_set(key,value);
    if (v==null && value!=null) {      // increased size()?
      if (getLoadFactor()>maxLoad_)
        rehash(table_.length*2);       // rehash if maximum load factor exceeded
    }
    return v;
  }
 
  public Value remove(Key key) {
    return _set(key,null);
  }
 
  @SuppressWarnings("unchecked")
  public Value find(Key key) {
    int hash=key.hashCode();
    hash = hash < 0 ? -hash : hash;
    int i=hash % table_.length;
    if (table_[i]!=null) {
      for (Bucket b=(Bucket) table_[i];b!=null;b=b.next) {
        if (b.key.equals(key))
          return b.value;
      }
    }
    return null;
  }
 
  public boolean contains(Key key) {
    return find(key)!=null;
  }
 
  @Override public String toString() {
    String s="{ ";
    for (Entry entry : entries())
      s+=(entry.key.toString()+"=>"+entry.value+",");
    s=s.substring(0,s.length()-1);
    return s+=" };";
  }
 
 
  public static void main(String args[]) {
    HashMap<String,Integer> map=new HashMap<String,Integer>();
 
    map.insert("a",1);
    map.insert("b",2);
    map.insert("c",3);
    map.insert("d",4);
    map.insert("e",5);
    map.insert("f",6);
    map.insert("g",7);
    map.insert("h",8);
 
    for (HashMap<String,Integer>.Entry entry : map.entries()) {
      System.out.println(entry.key+" => "+entry.value);
    }
    System.out.println(map);
    map.remove("a");
    System.out.println(map);
    System.out.println(map.find("c"));
    System.out.println(map.find("x"));
  }
}