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   Set keys;
   8
   9   public HashMap() {
  10     init(16, 0.75f);
  11   }
  12
  13   public HashMap(int initialCapacity) {
  14     init(initialCapacity, 0.75f);
  15   }
  16
  17   public HashMap(int initialCapacity, float loadFactor) {
  18     init(initialCapacity, loadFactor);
  19   }
  20
  21   private void init(int initialCapacity, float loadFactor) {
  22     table=new HashEntry[computeCapacity(initialCapacity)];
  23     this.loadFactor=loadFactor;
  24     this.numItems=0;
  25     this.threshold=(int)(loadFactor*table.length);
  26   }
  27
  28   private static int computeCapacity(int capacity) {
  29     int x=16;
  30     while(x<capacity)
  31       x=x<<1;
  32     return x;
  33   }
  34
  35   private static int hash(Object o, int length) {
  36     int orig=o.hashCode();
  37     orig=orig^(orig>>>22)^(orig>>>10);
  38     orig=orig^(orig>>>8)^(orig>>4);
  39     return orig&(length-1);
  40   }
  41
  42   void resize() {
  43     int newCapacity=table.length<<1;
  44     HashEntry[] oldtable=table;
  45     this.table=new HashEntry[newCapacity];
  46     this.threshold=(int) (newCapacity*loadFactor);
  47
  48     for(int i=0; i<oldtable.length; i++) {
  49       HashEntry e=oldtable[i];
  50       while(e!=null) {
  51     HashEntry next=e.next;
  52     int bin=hash(e.key, newCapacity);
  53     e.next=table[bin];
  54     table[bin]=e;
  55     e=next;
  56       }
  57     }
  58   }
  59
  60   public void clear() {
  61     for(int i=0;i<table.length;i++)
  62       table[i]=null;
  63     numItems=0;
  64   }
  65
  66   public boolean isEmpty() {
  67     return numItems==0;
  68   }
  69
  70   public int size() {
  71     return numItems;
  72   }
  73
  74   /* 0=keys, 1=values */
  75   public Iterator iterator(int type) {
  76     return (Iterator)(new HashMapIterator(this, type));
  77   }
  78
  79   Object remove(Object key) {
  80     int bin=hash(key, table.length);
  81     HashEntry ptr=table[bin];
  82     if (ptr!=null) {
  83       if (ptr.key.equals(key)) {
  84         table[bin]=ptr.next;
  85         numItems--;
  86         return ptr.value;
  87       }
  88       while(ptr.next!=null) {
  89         if (ptr.next.key.equals(key)) {
  90           Object oldvalue=ptr.value;
  91           ptr.next=ptr.next.next;
  92           numItems--;
  93           return oldvalue;
  94         }
  95         ptr=ptr.next;
  96       }
  97     }
  98     return null;
  99   }
 100
 101   Object get(Object key) {
 102     int bin=hash(key, table.length);
 103     HashEntry ptr=table[bin];
 104     while(ptr!=null) {
 105       if (ptr.key.equals(key)) {
 106         return ptr.value;
 107       }
 108       ptr=ptr.next;
 109     }
 110     return null;
 111   }
 112
 113   boolean containsKey(Object key) {
 114     int bin=hash(key, table.length);
 115     HashEntry ptr=table[bin];
 116     while(ptr!=null) {
 117       if (ptr.key.equals(key)) {
 118         return true;
 119       }
 120       ptr=ptr.next;
 121     }
 122     return false;
 123   }
 124
 125   Object put(Object key, Object value) {
 126     numItems++;
 127     if (numItems>threshold) {
 128       //Resize the table
 129       resize();
 130     }
 131     int bin=hash(key, table.length);
 132     HashEntry ptr=table[bin];
 133     while(ptr!=null) {
 134       if (ptr.key.equals(key)) {
 135         Object oldvalue=ptr.value;
 136         ptr.value=value;
 137         return oldvalue;
 138       }
 139       ptr=ptr.next;
 140     }
 141     HashEntry he=new HashEntry();
 142     he.value=value;
 143     he.key=key;
 144     he.next=table[bin];
 145     table[bin]=he;
 146     return null;
 147   }
 148
 149   public Collection values()
 150   {
 151     if (values == null)
 152       // We don't bother overriding many of the optional methods, as doing so
 153       // wouldn't provide any significant performance advantage.
 154       values = new AbstractCollection()
 155       {
 156
 157         public int size()
 158         {
 159           return size;
 160         }
 161
 162         public Iterator iterator()
 163         {
 164           // Cannot create the iterator directly, because of LinkedHashMap.
 165           return HashMapIterator(HashMap.this, 1);
 166         }
 167
 168         public void clear()
 169         {
 170           HashMap.this.clear();
 171         }
 172       };
 173     return values;
 174   }
 175
 176   public Set keySet()
 177   {
 178     if (keys == null)
 179       // Create an AbstractSet with custom implementations of those methods
 180       // that can be overridden easily and efficiently.
 181       keys = new AbstractSet()
 182       {
 183         public int size()
 184         {
 185           return size;
 186         }
 187
 188         public Iterator iterator()
 189         {
 190           // Cannot create the iterator directly, because of LinkedHashMap.
 191           //return HashMap.this.iterator(KEYS);
 192           return HashMapIterator(HashMap.this, 0);
 193         }
 194
 195         public void clear()
 196         {
 197           HashMap.this.clear();
 198         }
 199
 200         public boolean contains(Object o)
 201         {
 202           return containsKey(o);
 203         }
 204
 205         public boolean remove(Object o)
 206         {
 207           // Test against the size of the HashMap to determine if anything
 208           // really got removed. This is necessary because the return value
 209           // of HashMap.remove() is ambiguous in the null case.
 210           int oldsize = size;
 211           HashMap.this.remove(o);
 212           return oldsize != size;
 213         }
 214       };
 215     return keys;
 216   }
 217 }