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     /* 0=keys, 1=values */
  49     public HashMapIterator iterator(int type) {
  50         return new HashMapIterator(this, type);
  51     }
  52
  53     Object remove(Object key) {
  54         int bin=key.hashCode()%table.length;
  55         HashEntry ptr=table[bin];
  56         if (ptr.key==key) {
  57             table[bin]=ptr.next;
  58             numItems--;
  59             return ptr.value;
  60         }
  61         while(ptr.next!=null) {
  62             if (ptr.next.key==key) {
  63                 Object oldvalue=ptr.value;
  64                 ptr.next=ptr.next.next;
  65                 numItems--;
  66                 return oldvalue;
  67             }
  68         }
  69         return null;
  70     }
  71
  72     Object get(Object key) {
  73         int bin=key.hashCode()%table.length;
  74         HashEntry ptr=table[bin];
  75         while(ptr!=null) {
  76             if (ptr.key==key) {
  77                 return ptr.value;
  78             }
  79         }
  80         return null;
  81     }
  82
  83     boolean containsKey(Object key) {
  84         int bin=key.hashCode()%table.length;
  85         HashEntry ptr=table[bin];
  86         while(ptr!=null) {
  87             if (ptr.key==key) {
  88                 return true;
  89             }
  90         }
  91         return false;
  92     }
  93
  94     Object put(Object key, Object value) {
  95         numItems++;
  96         if (numItems>(loadFactor*table.length)) {
  97             //Resize the table
  98             resize();
  99         }
 100         int bin=key.hashCode()%table.length;
 101         HashEntry ptr=table[bin];
 102         while(ptr!=null) {
 103             if (ptr.key==key) {
 104                 Object oldvalue=ptr.value;
 105                 ptr.value=value;
 106                 return oldvalue;
 107             }
 108         }
 109         HashEntry he=new HashEntry();
 110         he.value=value;
 111         he.key=key;
 112         he.next=table[bin];
 113         table[bin]=he;
 114         return null;
 115     }
 116
 117 }