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     void resize() {
  25         int newCapacity=2*table.length+1;
  26         HashEntry[] newtable=new HashEntry[newCapacity];
  27         for(int i=0;i<table.length;i++) {
  28             HashEntry e=table[i];
  29             while(e!=null) {
  30                 HashEntry next=e.next;
  31                 int bin=e.key.hashCode()%newCapacity;
  32                 e.next=newtable[bin];
  33                 newtable[bin]=e;
  34                 e=next;
  35             }
  36         }
  37         this.table=newtable;
  38     }
  39
  40     public boolean isEmpty() {
  41         return numItems==0;
  42     }
  43
  44     public int size() {
  45         return numItems;
  46     }
  47
  48     Object remove(Object key) {
  49         int bin=key.hashCode()%table.length;
  50         HashEntry ptr=table[bin];
  51         if (ptr.key==key) {
  52             table[bin]=ptr.next;
  53             numItems--;
  54             return ptr.value;
  55         }
  56         while(ptr.next!=null) {
  57             if (ptr.next.key==key) {
  58                 Object oldvalue=ptr.value;
  59                 ptr.next=ptr.next.next;
  60                 numItems--;
  61                 return oldvalue;
  62             }
  63         }
  64         return null;
  65     }
  66
  67     Object get(Object key) {
  68         int bin=key.hashCode()%table.length;
  69         HashEntry ptr=table[bin];
  70         while(ptr!=null) {
  71             if (ptr.key==key) {
  72                 return ptr.value;
  73             }
  74         }
  75         return null;
  76     }
  77
  78     boolean containsKey(Object key) {
  79         int bin=key.hashCode()%table.length;
  80         HashEntry ptr=table[bin];
  81         while(ptr!=null) {
  82             if (ptr.key==key) {
  83                 return true;
  84             }
  85         }
  86         return false;
  87     }
  88
  89     Object put(Object key, Object value) {
  90         numItems++;
  91         if (numItems>(loadFactor*table.length)) {
  92             //Resize the table
  93             resize();
  94         }
  95         int bin=key.hashCode()%table.length;
  96         HashEntry ptr=table[bin];
  97         while(ptr!=null) {
  98             if (ptr.key==key) {
  99                 Object oldvalue=ptr.value;
 100                 ptr.value=value;
 101                 return oldvalue;
 102             }
 103         }
 104         HashEntry he=new HashEntry();
 105         he.value=value;
 106         he.key=key;
 107         he.next=table[bin];
 108         table[bin]=he;
 109         return null;
 110     }
 111
 112 }