Robust/src/ClassLibrary/DistributedHashMap.java

   1 public class DistributedHashMap {
   2   DistributedHashEntry[] table;
   3   float loadFactor;
   4   int secondcapacity;
   5
   6   public DistributedHashMap(int initialCapacity, int secondcapacity, float loadFactor) {
   7     init(initialCapacity, secondcapacity, loadFactor);
   8   }
   9
  10   private void init(int initialCapacity, int secondcapacity, float loadFactor) {
  11     table=global new DistributedHashEntry[initialCapacity];
  12     this.loadFactor=loadFactor;
  13     this.secondcapacity=secondcapacity;
  14   }
  15
  16   private static int hash1(int hashcode, int length) {
  17     int value=hashcode%length;
  18     if (value<0)
  19       return -value;
  20     else
  21       return value;
  22   }
  23
  24   private static int hash2(int hashcode, int length1, int length2) {
  25     int value=(hashcode*31)%length2;
  26     if (value<0)
  27       return -value;
  28     else
  29       return value;
  30   }
  31
  32   void resize(int index) {
  33     DHashEntry[] oldtable=table[index].array;
  34     int newCapacity=oldtable.length*2+1;
  35     DHashEntry [] newtable=global new DHashEntry[newCapacity];
  36     table[index].array=newtable;
  37
  38     for(int i=0; i<oldtable.length; i++) {
  39       DHashEntry e=oldtable[i];
  40       while(e!=null) {
  41         DHashEntry next=e.next;
  42         int bin=hash2(e.hashval, table.length, newCapacity);
  43         e.next=newtable[bin];
  44         newtable[bin]=e;
  45         e=next;
  46       }
  47     }
  48   }
  49
  50   Object remove(Object key) {
  51     int hashcode=key.hashCode();
  52     int index1=hash1(hashcode, table.length);
  53     DistributedHashEntry dhe=table[index1];
  54     if (dhe==null)
  55       return null;
  56     int index2=hash2(hashcode, table.length, dhe.array.length);
  57     DHashEntry ptr=dhe.array[index2];
  58
  59     if (ptr!=null) {
  60       if (ptr.hashval==hashcode&&ptr.key.equals(key)) {
  61         dhe.array[index2]=ptr.next;
  62         dhe.count--;
  63         return ptr.value;
  64       }
  65       while(ptr.next!=null) {
  66         if (ptr.hashval==hashcode&&ptr.next.key.equals(key)) {
  67           Object oldvalue=ptr.value;
  68           ptr.next=ptr.next.next;
  69           dhe.count--;
  70           return oldvalue;
  71         }
  72         ptr=ptr.next;
  73       }
  74     }
  75     return null;
  76   }
  77
  78   Object get(Object key) {
  79     int hashcode=key.hashCode();
  80     int index1=hash1(hashcode, table.length);
  81     DistributedHashEntry dhe=table[index1];
  82     if (dhe==null)
  83       return null;
  84
  85     int index2=hash2(hashcode, table.length, dhe.array.length);
  86     DHashEntry ptr=dhe.array[index2];
  87
  88     while(ptr!=null) {
  89       if (ptr.hashval==hashcode
  90           &&ptr.key.equals(key)) {
  91         return ptr.value;
  92       }
  93       ptr=ptr.next;
  94     }
  95     return null;
  96   }
  97
  98   boolean containsKey(Object key) {
  99     int hashcode=key.hashCode();
 100     int index1=hash1(hashcode, table.length);
 101     DistributedHashEntry dhe=table[index1];
 102     if (dhe==null)
 103       return false;
 104     int index2=hash2(hashcode, table.length, dhe.array.length);
 105     DHashEntry ptr=dhe.array[index2];
 106
 107     while(ptr!=null) {
 108       if (ptr.hashval==hashcode
 109           &&ptr.key.equals(key)) {
 110         return true;
 111       }
 112       ptr=ptr.next;
 113     }
 114     return false;
 115   }
 116
 117   Object put(Object key, Object value) {
 118     int hashcode=key.hashCode();
 119     int index1=hash1(hashcode, table.length);
 120     DistributedHashEntry dhe=table[index1];
 121     if (dhe==null) {
 122       dhe=global new DistributedHashEntry(secondcapacity);
 123       table[index1]=dhe;
 124     }
 125     int index2=hash2(hashcode, table.length, dhe.array.length);
 126     DHashEntry ptr=dhe.array[index2];
 127
 128     while(ptr!=null) {
 129       if (ptr.hashval==hashcode&&ptr.key.equals(key)) {
 130         Object oldvalue=ptr.value;
 131         ptr.value=value;
 132         return oldvalue;
 133       }
 134       ptr=ptr.next;
 135     }
 136
 137     DHashEntry he=global new DHashEntry();
 138     he.value=value;
 139     he.key=key;
 140     he.hashval=hashcode;
 141     he.next=dhe.array[index2];
 142     dhe.array[index2]=he;
 143
 144     dhe.count++;
 145     if (dhe.count>(loadFactor*dhe.array.length)) {
 146       //Resize the table
 147       resize(index1);
 148     }
 149     return null;
 150   }
 151 }
 152
 153
 154 class DistributedHashEntry {
 155   public DistributedHashEntry(int capacity) {
 156     array=global new DHashEntry[capacity];
 157   }
 158   int count;
 159   DHashEntry[] array;
 160 }
 161
 162
 163 class DHashEntry {
 164   public DHashEntry() {
 165   }
 166   int hashval;
 167   Object key;
 168   Object value;
 169   DHashEntry next;
 170 }