Robust/src/ClassLibrary/HashMap.java

   1 public class HashMap {
   2   HashEntry[] table;
   3   float loadFactor;
   4   int numItems;
   5
   6   public HashMap() {
   7     init(16, 0.75f);
   8   }
   9
  10   public HashMap(int initialCapacity) {
  11     init(initialCapacity, 0.75f);
  12   }
  13
  14   public HashMap(int initialCapacity, float loadFactor) {
  15     init(initialCapacity, loadFactor);
  16   }
  17
  18   private void init(int initialCapacity, float loadFactor) {
  19     table=new HashEntry[initialCapacity];
  20     this.loadFactor=loadFactor;
  21     this.numItems=0;
  22   }
  23
  24   private int hash(Object o) {
  25     if (o==null)
  26       return 0;
  27     int value=o.hashCode()%table.length;
  28     if (value<0)
  29       return -value;
  30     return value;
  31   }
  32
  33   void resize() {
  34     int newCapacity=2*table.length+1;
  35     HashEntry[] oldtable=table;
  36     this.table=new HashEntry[newCapacity];
  37
  38     for(int i=0; i<oldtable.length; i++) {
  39       HashEntry e=oldtable[i];
  40       while(e!=null) {
  41         HashEntry next=e.next;
  42         int bin=hash(e.key);
  43         e.next=table[bin];
  44         table[bin]=e;
  45         e=next;
  46       }
  47     }
  48   }
  49
  50   public boolean isEmpty() {
  51     return numItems==0;
  52   }
  53
  54   public int size() {
  55     return numItems;
  56   }
  57
  58   /* 0=keys, 1=values */
  59   public HashMapIterator iterator(int type) {
  60     return new HashMapIterator(this, type);
  61   }
  62
  63   Object remove(Object key) {
  64     int bin=hash(key);
  65     HashEntry ptr=table[bin];
  66     if (ptr!=null) {
  67       if (ptr.key.equals(key)) {
  68         table[bin]=ptr.next;
  69         numItems--;
  70         return ptr.value;
  71       }
  72       while(ptr.next!=null) {
  73         if (ptr.next.key.equals(key)) {
  74           Object oldvalue=ptr.value;
  75           ptr.next=ptr.next.next;
  76           numItems--;
  77           return oldvalue;
  78         }
  79         ptr=ptr.next;
  80       }
  81     }
  82     return null;
  83   }
  84
  85   Object get(Object key) {
  86     int bin=hash(key);
  87     HashEntry ptr=table[bin];
  88     while(ptr!=null) {
  89       if (ptr.key.equals(key)) {
  90         return ptr.value;
  91       }
  92       ptr=ptr.next;
  93     }
  94     return null;
  95   }
  96
  97   boolean containsKey(Object key) {
  98     int bin=hash(key);
  99     HashEntry ptr=table[bin];
 100     while(ptr!=null) {
 101       if (ptr.key.equals(key)) {
 102         return true;
 103       }
 104       ptr=ptr.next;
 105     }
 106     return false;
 107   }
 108
 109   Object put(Object key, Object value) {
 110     numItems++;
 111     if (numItems>(loadFactor*table.length)) {
 112       //Resize the table
 113       resize();
 114     }
 115     int bin=hash(key);
 116     HashEntry ptr=table[bin];
 117     while(ptr!=null) {
 118       if (ptr.key.equals(key)) {
 119         Object oldvalue=ptr.value;
 120         ptr.value=value;
 121         return oldvalue;
 122       }
 123       ptr=ptr.next;
 124     }
 125     HashEntry he=new HashEntry();
 126     he.value=value;
 127     he.key=key;
 128     he.next=table[bin];
 129     table[bin]=he;
 130     return null;
 131   }
 132 }