1 7 8 package java.util; 9 import java.io.*; 10 11 126 127 public class LinkedHashMap<K,V> 128 extends HashMap <K,V> 129 implements Map <K,V> 130 { 131 132 private static final long serialVersionUID = 3801124242820219131L; 133 134 137 private transient Entry<K,V> header; 138 139 145 private final boolean accessOrder; 146 147 156 public LinkedHashMap(int initialCapacity, float loadFactor) { 157 super(initialCapacity, loadFactor); 158 accessOrder = false; 159 } 160 161 168 public LinkedHashMap(int initialCapacity) { 169 super(initialCapacity); 170 accessOrder = false; 171 } 172 173 177 public LinkedHashMap() { 178 super(); 179 accessOrder = false; 180 } 181 182 191 public LinkedHashMap(Map <? extends K, ? extends V> m) { 192 super(m); 193 accessOrder = false; 194 } 195 196 207 public LinkedHashMap(int initialCapacity, 208 float loadFactor, 209 boolean accessOrder) { 210 super(initialCapacity, loadFactor); 211 this.accessOrder = accessOrder; 212 } 213 214 219 void init() { 220 header = new Entry<K,V>(-1, null, null, null); 221 header.before = header.after = header; 222 } 223 224 229 void transfer(HashMap.Entry [] newTable) { 230 int newCapacity = newTable.length; 231 for (Entry<K,V> e = header.after; e != header; e = e.after) { 232 int index = indexFor(e.hash, newCapacity); 233 e.next = newTable[index]; 234 newTable[index] = e; 235 } 236 } 237 238 239 247 public boolean containsValue(Object value) { 248 if (value==null) { 250 for (Entry e = header.after; e != header; e = e.after) 251 if (e.value==null) 252 return true; 253 } else { 254 for (Entry e = header.after; e != header; e = e.after) 255 if (value.equals(e.value)) 256 return true; 257 } 258 return false; 259 } 260 261 272 public V get(Object key) { 273 Entry<K,V> e = (Entry<K,V>)getEntry(key); 274 if (e == null) 275 return null; 276 e.recordAccess(this); 277 return e.value; 278 } 279 280 283 public void clear() { 284 super.clear(); 285 header.before = header.after = header; 286 } 287 288 291 private static class Entry<K,V> extends HashMap.Entry <K,V> { 292 Entry<K,V> before, after; 294 295 Entry(int hash, K key, V value, HashMap.Entry <K,V> next) { 296 super(hash, key, value, next); 297 } 298 299 302 private void remove() { 303 before.after = after; 304 after.before = before; 305 } 306 307 310 private void addBefore(Entry<K,V> existingEntry) { 311 after = existingEntry; 312 before = existingEntry.before; 313 before.after = this; 314 after.before = this; 315 } 316 317 323 void recordAccess(HashMap <K,V> m) { 324 LinkedHashMap <K,V> lm = (LinkedHashMap <K,V>)m; 325 if (lm.accessOrder) { 326 lm.modCount++; 327 remove(); 328 addBefore(lm.header); 329 } 330 } 331 332 void recordRemoval(HashMap <K,V> m) { 333 remove(); 334 } 335 } 336 337 private abstract class LinkedHashIterator<T> implements Iterator <T> { 338 Entry<K,V> nextEntry = header.after; 339 Entry<K,V> lastReturned = null; 340 341 346 int expectedModCount = modCount; 347 348 public boolean hasNext() { 349 return nextEntry != header; 350 } 351 352 public void remove() { 353 if (lastReturned == null) 354 throw new IllegalStateException (); 355 if (modCount != expectedModCount) 356 throw new ConcurrentModificationException (); 357 358 LinkedHashMap.this.remove(lastReturned.key); 359 lastReturned = null; 360 expectedModCount = modCount; 361 } 362 363 Entry<K,V> nextEntry() { 364 if (modCount != expectedModCount) 365 throw new ConcurrentModificationException (); 366 if (nextEntry == header) 367 throw new NoSuchElementException (); 368 369 Entry<K,V> e = lastReturned = nextEntry; 370 nextEntry = e.after; 371 return e; 372 } 373 } 374 375 private class KeyIterator extends LinkedHashIterator<K> { 376 public K next() { return nextEntry().getKey(); } 377 } 378 379 private class ValueIterator extends LinkedHashIterator<V> { 380 public V next() { return nextEntry().value; } 381 } 382 383 private class EntryIterator extends LinkedHashIterator<Map.Entry <K,V>> { 384 public Map.Entry <K,V> next() { return nextEntry(); } 385 } 386 387 Iterator <K> newKeyIterator() { return new KeyIterator(); } 389 Iterator <V> newValueIterator() { return new ValueIterator(); } 390 Iterator <Map.Entry <K,V>> newEntryIterator() { return new EntryIterator(); } 391 392 397 void addEntry(int hash, K key, V value, int bucketIndex) { 398 createEntry(hash, key, value, bucketIndex); 399 400 Entry<K,V> eldest = header.after; 402 if (removeEldestEntry(eldest)) { 403 removeEntryForKey(eldest.key); 404 } else { 405 if (size >= threshold) 406 resize(2 * table.length); 407 } 408 } 409 410 414 void createEntry(int hash, K key, V value, int bucketIndex) { 415 HashMap.Entry <K,V> old = table[bucketIndex]; 416 Entry<K,V> e = new Entry<K,V>(hash, key, value, old); 417 table[bucketIndex] = e; 418 e.addBefore(header); 419 size++; 420 } 421 422 463 protected boolean removeEldestEntry(Map.Entry <K,V> eldest) { 464 return false; 465 } 466 } 467 | Popular Tags |