1 4 package gnu.kawa.util; 5 6 9 10 public class GeneralHashTable 11 { 13 protected HashNode[] table; 14 protected int mask; 15 protected int num_bindings; 16 17 public GeneralHashTable () 18 { 19 this(64); 20 } 21 22 public GeneralHashTable (int capacity) 23 { 24 int log2Size = 4; 25 while (capacity > (1 << log2Size)) 26 log2Size++; 27 capacity = 1 << log2Size; 28 table = new HashNode[capacity]; 29 mask = capacity - 1; 30 } 31 32 33 protected HashNode makeEntry (Object key, int hash, Object value) 34 { 35 HashNode node = new HashNode(); 36 node.key = key; 37 node.hash = hash; 38 node.value = value; 39 return node; 40 } 41 42 45 public int hash (Object key) 46 { 47 return key == null ? 0 : key.hashCode(); 49 } 50 51 public int hash (HashNode node) 52 { 53 return node.hash; 55 } 56 57 public boolean matches (Object key, int hash, HashNode node) 58 { 59 return node.hash == hash && matches(node.getKey(), key); 60 } 61 62 66 public boolean matches (Object value1, Object value2) 67 { 68 return value1 == value2 || (value1 != null && value1.equals(value2)); 70 } 71 72 public Object get (Object key, Object defaultValue) 73 { 74 int hash = hash(key); 75 int index = hash & this.mask; 76 for (HashNode node = table[index]; 77 node != null; node = node.next) 78 { 79 if (matches(key, hash, node)) 80 return node.getValue(); 81 } 82 return defaultValue; 83 } 84 85 public HashNode getNode (Object key) 86 { 87 int hash = hash(key); 88 int index = hash & this.mask; 89 for (HashNode node = table[index]; 90 node != null; node = node.next) 91 { 92 if (matches(key, hash, node)) 93 return node; 94 } 95 return null; 96 } 97 98 public Object put (Object key, Object value) 99 { 100 return put(key, hash(key), value); 101 } 102 103 public Object put (Object key, int hash, Object value) 104 { 105 int index = hash & mask; 106 HashNode first = table[index]; 107 HashNode node = first; 108 for (;;) 109 { 110 if (node == null) 111 { 112 if (++num_bindings >= table.length) 113 { 114 rehash(); 115 index = hash & mask; 116 first = table[index]; 117 } 118 node = makeEntry(key, hash, value); 119 node.next = first; 120 table[index] = node; 121 return null; 122 } 123 else if (matches(key, hash, node)) 124 { 125 return node.setValue(value); 126 } 127 node = node.next; 128 } 129 } 130 131 public Object remove (Object key) 132 { 133 int hash = hash(key); 134 int index = hash & this.mask; 135 HashNode prev = null; 136 HashNode node = table[index]; 137 while (node != null) 138 { 139 HashNode next = node.next; 140 if (matches(key, hash, node)) 141 { 142 if (prev == null) 143 table[index] = next; 144 else 145 prev.next = node; 146 num_bindings--; 147 return node.getValue(); 148 } 149 prev = node; 150 node = next; 151 } 152 return null; 153 } 154 155 protected void rehash () 156 { 157 HashNode[] oldTable = table; 158 int oldCapacity = oldTable.length; 159 int newCapacity = 2 * oldCapacity; 160 HashNode[] newTable = new HashNode[newCapacity]; 161 int newMask = newCapacity - 1; 162 for (int i = oldCapacity; --i >= 0;) 163 { 164 HashNode chain = oldTable[i]; 165 if (chain != null && chain.next != null) 166 { 167 HashNode prev = null; 172 do 173 { 174 HashNode node = chain; 175 chain = node.next; 176 node.next = prev; 177 prev = node; 178 } 179 while (chain != null); 180 chain = prev; 181 } 182 183 for (HashNode element = chain; element != null; ) 184 { 185 HashNode next = element.next; 186 int hash = hash(element); 187 int j = hash & newMask; 188 HashNode head = newTable[j]; 189 element.next = head; 190 newTable[j] = element; 191 element = next; 192 } 193 } 194 table = newTable; 195 mask = newMask; 196 } 197 198 public void clear () 199 { 200 HashNode[] t = this.table; 201 for (int i = t.length; --i >= 0; ) 202 t[i] = null; 203 num_bindings = 0; 204 } 205 206 public int size () 207 { 208 return num_bindings; 209 } 210 211 protected static HashNode next (HashNode node) 212 { 213 return node.next; 214 } 215 } 216 | Popular Tags |