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 }