Robust/src/ClassLibrary/HashMap.java

   1 public class HashMap {
   2   HashEntry[] table;
   3   float loadFactor;
   4   int numItems;
   5   int threshold;
   6
   7   public HashMap() {
   8     init(16, 0.75f);
   9   }
  10
  11   public HashMap(int initialCapacity) {
  12     init(initialCapacity, 0.75f);
  13   }
  14
  15   public HashMap(int initialCapacity, float loadFactor) {
  16     init(initialCapacity, loadFactor);
  17   }
  18
  19   private void init(int initialCapacity, float loadFactor) {
  20     table=new HashEntry[computeCapacity(initialCapacity)];
  21     this.loadFactor=loadFactor;
  22     this.numItems=0;
  23     this.threshold=(int)(loadFactor*table.length);
  24   }
  25
  26   private static int computeCapacity(int capacity) {
  27     int x=16;
  28     while(x<capacity)
  29       x=x<<1;
  30     return x;
  31   }
  32
  33   private static int hash(Object o, int length) {
  34     int orig=o.hashCode();
  35     orig=orig^(orig>>>22)^(orig>>>10);
  36     orig=orig^(orig>>>8)^(orig>>4);
  37     return orig&(length-1);
  38   }
  39
  40   void resize() {
  41     int newCapacity=table.length<<1;
  42     HashEntry[] oldtable=table;
  43     this.table=new HashEntry[newCapacity];
  44     this.threshold=(int) (newCapacity*loadFactor);
  45
  46     for(int i=0; i<oldtable.length; i++) {
  47       HashEntry e=oldtable[i];
  48       while(e!=null) {
  49         HashEntry next=e.next;
  50         int bin=hash(e.key, newCapacity);
  51         e.next=table[bin];
  52         table[bin]=e;
  53         e=next;
  54       }
  55     }
  56   }
  57
  58   public void clear() {
  59     for(int i=0; i<table.length; i++)
  60       table[i]=null;
  61     numItems=0;
  62   }
  63
  64   public boolean isEmpty() {
  65     return numItems==0;
  66   }
  67
  68   public int size() {
  69     return numItems;
  70   }
  71
  72   /* 0=keys, 1=values */
  73   public HashMapIterator iterator(int type) {
  74     return (new HashMapIterator(this, type));
  75   }
  76
  77   Object remove(Object key) {
  78     int bin=hash(key, table.length);
  79     HashEntry ptr=table[bin];
  80     if (ptr!=null) {
  81       if (ptr.key.equals(key)) {
  82         table[bin]=ptr.next;
  83         numItems--;
  84         return ptr.value;
  85       }
  86       while(ptr.next!=null) {
  87         if (ptr.next.key.equals(key)) {
  88           Object oldvalue=ptr.value;
  89           ptr.next=ptr.next.next;
  90           numItems--;
  91           return oldvalue;
  92         }
  93         ptr=ptr.next;
  94       }
  95     }
  96     return null;
  97   }
  98
  99   Object get(Object key) {
 100     int bin=hash(key, table.length);
 101     HashEntry ptr=table[bin];
 102     while(ptr!=null) {
 103       if (ptr.key.equals(key)) {
 104         return ptr.value;
 105       }
 106       ptr=ptr.next;
 107     }
 108     return null;
 109   }
 110
 111   boolean containsKey(Object key) {
 112     int bin=hash(key, table.length);
 113     HashEntry ptr=table[bin];
 114     while(ptr!=null) {
 115       if (ptr.key.equals(key)) {
 116         return true;
 117       }
 118       ptr=ptr.next;
 119     }
 120     return false;
 121   }
 122
 123   Object put(Object key, Object value) {
 124     numItems++;
 125     if (numItems>threshold) {
 126       //Resize the table
 127       resize();
 128     }
 129     int bin=hash(key, table.length);
 130     HashEntry ptr=table[bin];
 131     while(ptr!=null) {
 132       if (ptr.key.equals(key)) {
 133         Object oldvalue=ptr.value;
 134         ptr.value=value;
 135         return oldvalue;
 136       }
 137       ptr=ptr.next;
 138     }
 139     HashEntry he=new HashEntry();
 140     he.value=value;
 141     he.key=key;
 142     he.next=table[bin];
 143     table[bin]=he;
 144     return null;
 145   }
 146 }