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.key.equals(key)) {
  67             table[bin]=ptr.next;
  68             numItems--;
  69             return ptr.value;
  70         }
  71         while(ptr.next!=null) {
  72             if (ptr.next.key.equals(key)) {
  73                 Object oldvalue=ptr.value;
  74                 ptr.next=ptr.next.next;
  75                 numItems--;
  76                 return oldvalue;
  77             }
  78             ptr=ptr.next;
  79         }
  80         return null;
  81     }
  82
  83     Object get(Object key) {
  84         int bin=hash(key);
  85         HashEntry ptr=table[bin];
  86         while(ptr!=null) {
  87             if (ptr.key.equals(key)) {
  88                 return ptr.value;
  89             }
  90             ptr=ptr.next;
  91         }
  92         return null;
  93     }
  94
  95     boolean containsKey(Object key) {
  96         int bin=hash(key);
  97         HashEntry ptr=table[bin];
  98         while(ptr!=null) {
  99             if (ptr.key.equals(key)) {
 100                 return true;
 101             }
 102             ptr=ptr.next;
 103         }
 104         return false;
 105     }
 106
 107     Object put(Object key, Object value) {
 108         numItems++;
 109         if (numItems>(loadFactor*table.length)) {
 110             //Resize the table
 111             resize();
 112         }
 113         int bin=hash(key);
 114         HashEntry ptr=table[bin];
 115         while(ptr!=null) {
 116             if (ptr.key.equals(key)) {
 117                 Object oldvalue=ptr.value;
 118                 ptr.value=value;
 119                 return oldvalue;
 120             }
 121             ptr=ptr.next;
 122         }
 123         HashEntry he=new HashEntry();
 124         he.value=value;
 125         he.key=key;
 126         he.next=table[bin];
 127         table[bin]=he;
 128         return null;
 129     }
 130 }