Robust/src/ClassLibrary/MGC/HashMap.java

   1 public class HashMap implements Map {
   2   HashEntry[] table;
   3   float loadFactor;
   4   int numItems;
   5   int threshold;
   6   Collection values;
   7
   8   public HashMap() {
   9     init(16, 0.75f);
  10   }
  11
  12   public HashMap(int initialCapacity) {
  13     init(initialCapacity, 0.75f);
  14   }
  15
  16   public HashMap(int initialCapacity, float loadFactor) {
  17     init(initialCapacity, loadFactor);
  18   }
  19
  20   private void init(int initialCapacity, float loadFactor) {
  21     table=new HashEntry[computeCapacity(initialCapacity)];
  22     this.loadFactor=loadFactor;
  23     this.numItems=0;
  24     this.threshold=(int)(loadFactor*table.length);
  25   }
  26
  27   private static int computeCapacity(int capacity) {
  28     int x=16;
  29     while(x<capacity)
  30       x=x<<1;
  31     return x;
  32   }
  33
  34   private static int hash(Object o, int length) {
  35     int orig=o.hashCode();
  36     orig=orig^(orig>>>22)^(orig>>>10);
  37     orig=orig^(orig>>>8)^(orig>>4);
  38     return orig&(length-1);
  39   }
  40
  41   void resize() {
  42     int newCapacity=table.length<<1;
  43     HashEntry[] oldtable=table;
  44     this.table=new HashEntry[newCapacity];
  45     this.threshold=(int) (newCapacity*loadFactor);
  46
  47     for(int i=0; i<oldtable.length; i++) {
  48       HashEntry e=oldtable[i];
  49       while(e!=null) {
  50     HashEntry next=e.next;
  51     int bin=hash(e.key, newCapacity);
  52     e.next=table[bin];
  53     table[bin]=e;
  54     e=next;
  55       }
  56     }
  57   }
  58
  59   public void clear() {
  60     for(int i=0;i<table.length;i++)
  61       table[i]=null;
  62     numItems=0;
  63   }
  64
  65   public boolean isEmpty() {
  66     return numItems==0;
  67   }
  68
  69   public int size() {
  70     return numItems;
  71   }
  72
  73   /* 0=keys, 1=values */
  74   public Iterator iterator(int type) {
  75     return (Iterator)(new HashMapIterator(this, type));
  76   }
  77
  78   Object remove(Object key) {
  79     int bin=hash(key, table.length);
  80     HashEntry ptr=table[bin];
  81     if (ptr!=null) {
  82       if (ptr.key.equals(key)) {
  83         table[bin]=ptr.next;
  84         numItems--;
  85         return ptr.value;
  86       }
  87       while(ptr.next!=null) {
  88         if (ptr.next.key.equals(key)) {
  89           Object oldvalue=ptr.value;
  90           ptr.next=ptr.next.next;
  91           numItems--;
  92           return oldvalue;
  93         }
  94         ptr=ptr.next;
  95       }
  96     }
  97     return null;
  98   }
  99
 100   Object get(Object key) {
 101     int bin=hash(key, table.length);
 102     HashEntry ptr=table[bin];
 103     while(ptr!=null) {
 104       if (ptr.key.equals(key)) {
 105         return ptr.value;
 106       }
 107       ptr=ptr.next;
 108     }
 109     return null;
 110   }
 111
 112   boolean containsKey(Object key) {
 113     int bin=hash(key, table.length);
 114     HashEntry ptr=table[bin];
 115     while(ptr!=null) {
 116       if (ptr.key.equals(key)) {
 117         return true;
 118       }
 119       ptr=ptr.next;
 120     }
 121     return false;
 122   }
 123
 124   Object put(Object key, Object value) {
 125     numItems++;
 126     if (numItems>threshold) {
 127       //Resize the table
 128       resize();
 129     }
 130     int bin=hash(key, table.length);
 131     HashEntry ptr=table[bin];
 132     while(ptr!=null) {
 133       if (ptr.key.equals(key)) {
 134         Object oldvalue=ptr.value;
 135         ptr.value=value;
 136         return oldvalue;
 137       }
 138       ptr=ptr.next;
 139     }
 140     HashEntry he=new HashEntry();
 141     he.value=value;
 142     he.key=key;
 143     he.next=table[bin];
 144     table[bin]=he;
 145     return null;
 146   }
 147
 148   public Collection values()
 149   {
 150     if (values == null)
 151       // We don't bother overriding many of the optional methods, as doing so
 152       // wouldn't provide any significant performance advantage.
 153       values = new AbstractCollection()
 154       {
 155         HashMap map;
 156
 157         public AbstractCollection(HashMap m) {
 158           this.map = map;
 159         }
 160
 161         public int size()
 162         {
 163           return size;
 164         }
 165
 166         public Iterator iterator()
 167         {
 168           // Cannot create the iterator directly, because of LinkedHashMap.
 169           return HashMapIterator(map, 1);
 170         }
 171
 172         public void clear()
 173         {
 174           map.clear();
 175         }
 176       };
 177     return values;
 178   }
 179 }