38 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to 39 * the invocation.) 40 * 41 * <p>This implementation spares its clients from the unspecified, generally 42 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}), 43 * without incurring the increased cost associated with {@link TreeMap}. It 44 * can be used to produce a copy of a map that has the same order as the 45 * original, regardless of the original map's implementation: 46 * <pre> 47 * void foo(Map m) { 48 * Map copy = new LinkedHashMap(m); 49 * ... 50 * } 51 * </pre> 52 * This technique is particularly useful if a module takes a map on input, 53 * copies it, and later returns results whose order is determined by that of 54 * the copy. (Clients generally appreciate having things returned in the same 55 * order they were presented.) 56 * 57 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is 58 * provided to create a linked hash map whose order of iteration is the order 59 * in which its entries were last accessed, from least-recently accessed to 60 * most-recently (<i>access-order</i>). This kind of map is well-suited to 61 * building LRU caches. Invoking the <tt>put</tt> or <tt>get</tt> method 62 * results in an access to the corresponding entry (assuming it exists after 63 * the invocation completes). The <tt>putAll</tt> method generates one entry 64 * access for each mapping in the specified map, in the order that key-value 65 * mappings are provided by the specified map's entry set iterator. <i>No 66 * other methods generate entry accesses.</i> In particular, operations on 67 * collection-views do <i>not</i> affect the order of iteration of the backing 68 * map. 69 * 70 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to 71 * impose a policy for removing stale mappings automatically when new mappings 72 * are added to the map. 73 * 74 * <p>This class provides all of the optional <tt>Map</tt> operations, and 75 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time 76 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and 77 * <tt>remove</tt>), assuming the hash function disperses elements 78 * properly among the buckets. Performance is likely to be just slightly 79 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the 80 * linked list, with one exception: Iteration over the collection-views 226 */ 227 public LinkedHashMap(int initialCapacity, 228 float loadFactor, 229 boolean accessOrder) { 230 super(initialCapacity, loadFactor); 231 this.accessOrder = accessOrder; 232 } 233 234 /** 235 * Called by superclass constructors and pseudoconstructors (clone, 236 * readObject) before any entries are inserted into the map. Initializes 237 * the chain. 238 */ 239 @Override 240 void init() { 241 header = new Entry<>(-1, null, null, null); 242 header.before = header.after = header; 243 } 244 245 /** 246 * Transfers all entries to new table array. This method is called 247 * by superclass resize. It is overridden for performance, as it is 248 * faster to iterate using our linked list. 249 */ 250 @Override 251 @SuppressWarnings("unchecked") 252 void transfer(HashMap.Entry[] newTable) { 253 int newCapacity = newTable.length; 254 for (Entry<K,V> e = header.after; e != header; e = e.after) { 255 int index = indexFor(e.hash, newCapacity); 256 e.next = (HashMap.Entry<K,V>)newTable[index]; 257 newTable[index] = e; 258 } 259 } 260 261 262 /** 263 * Returns <tt>true</tt> if this map maps one or more keys to the 264 * specified value. 265 * 266 * @param value value whose presence in this map is to be tested 267 * @return <tt>true</tt> if this map maps one or more keys to the 268 * specified value 269 */ 270 public boolean containsValue(Object value) { 271 // Overridden to take advantage of faster iterator 272 if (value==null) { 273 for (Entry<?,?> e = header.after; e != header; e = e.after) 274 if (e.value==null) 275 return true; 276 } else { 277 for (Entry<?,?> e = header.after; e != header; e = e.after) 278 if (value.equals(e.value)) 279 return true; 280 } 281 return false; 282 } 303 e.recordAccess(this); 304 return e.value; 305 } 306 307 /** 308 * Removes all of the mappings from this map. 309 * The map will be empty after this call returns. 310 */ 311 public void clear() { 312 super.clear(); 313 header.before = header.after = header; 314 } 315 316 /** 317 * LinkedHashMap entry. 318 */ 319 private static class Entry<K,V> extends HashMap.Entry<K,V> { 320 // These fields comprise the doubly linked list used for iteration. 321 Entry<K,V> before, after; 322 323 Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { 324 super(hash, key, value, next); 325 } 326 327 /** 328 * Removes this entry from the linked list. 329 */ 330 private void remove() { 331 before.after = after; 332 after.before = before; 333 } 334 335 /** 336 * Inserts this entry before the specified existing entry in the list. 337 */ 338 private void addBefore(Entry<K,V> existingEntry) { 339 after = existingEntry; 340 before = existingEntry.before; 341 before.after = this; 342 after.before = this; 343 } 344 345 /** 346 * This method is invoked by the superclass whenever the value 347 * of a pre-existing entry is read by Map.get or modified by Map.set. 348 * If the enclosing Map is access-ordered, it moves the entry 349 * to the end of the list; otherwise, it does nothing. 350 */ 351 void recordAccess(HashMap<K,V> m) { 352 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 353 if (lm.accessOrder) { 354 lm.modCount++; 355 remove(); 356 addBefore(lm.header); 357 } 358 } 359 360 void recordRemoval(HashMap<K,V> m) { 361 remove(); 362 } 363 } 364 365 private abstract class LinkedHashIterator<T> implements Iterator<T> { 366 Entry<K,V> nextEntry = header.after; 367 Entry<K,V> lastReturned = null; 405 } 406 407 private class ValueIterator extends LinkedHashIterator<V> { 408 public V next() { return nextEntry().value; } 409 } 410 411 private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { 412 public Map.Entry<K,V> next() { return nextEntry(); } 413 } 414 415 // These Overrides alter the behavior of superclass view iterator() methods 416 Iterator<K> newKeyIterator() { return new KeyIterator(); } 417 Iterator<V> newValueIterator() { return new ValueIterator(); } 418 Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } 419 420 /** 421 * This override alters behavior of superclass put method. It causes newly 422 * allocated entry to get inserted at the end of the linked list and 423 * removes the eldest entry if appropriate. 424 */ 425 void addEntry(int hash, K key, V value, int bucketIndex) { 426 super.addEntry(hash, key, value, bucketIndex); 427 428 // Remove eldest entry if instructed 429 Entry<K,V> eldest = header.after; 430 if (removeEldestEntry(eldest)) { 431 removeEntryForKey(eldest.key); 432 } 433 } 434 435 /** 436 * This override differs from addEntry in that it doesn't resize the 437 * table or remove the eldest entry. 438 */ 439 void createEntry(int hash, K key, V value, int bucketIndex) { 440 @SuppressWarnings("unchecked") 441 HashMap.Entry<K,V> old = (HashMap.Entry<K,V>)table[bucketIndex]; 442 Entry<K,V> e = new Entry<>(hash, key, value, old); 443 table[bucketIndex] = e; 444 e.addBefore(header); 445 size++; 446 } 447 448 /** 449 * Returns <tt>true</tt> if this map should remove its eldest entry. 450 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after 451 * inserting a new entry into the map. It provides the implementor 452 * with the opportunity to remove the eldest entry each time a new one 453 * is added. This is useful if the map represents a cache: it allows 454 * the map to reduce memory consumption by deleting stale entries. 455 * 456 * <p>Sample use: this override will allow the map to grow up to 100 457 * entries and then delete the eldest entry each time a new entry is 458 * added, maintaining a steady state of 100 entries. 459 * <pre> 460 * private static final int MAX_ENTRIES = 100; 461 * 462 * protected boolean removeEldestEntry(Map.Entry eldest) { 463 * return size() > MAX_ENTRIES; 464 * } 465 * </pre> | 38 * <tt>m.containsKey(k)</tt> would return <tt>true</tt> immediately prior to 39 * the invocation.) 40 * 41 * <p>This implementation spares its clients from the unspecified, generally 42 * chaotic ordering provided by {@link HashMap} (and {@link Hashtable}), 43 * without incurring the increased cost associated with {@link TreeMap}. It 44 * can be used to produce a copy of a map that has the same order as the 45 * original, regardless of the original map's implementation: 46 * <pre> 47 * void foo(Map m) { 48 * Map copy = new LinkedHashMap(m); 49 * ... 50 * } 51 * </pre> 52 * This technique is particularly useful if a module takes a map on input, 53 * copies it, and later returns results whose order is determined by that of 54 * the copy. (Clients generally appreciate having things returned in the same 55 * order they were presented.) 56 * 57 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is 58 * provided to create a <tt>LinkedHashMap</tt> whose order of iteration is the 59 * order in which its entries were last accessed, from least-recently accessed 60 * to most-recently (<i>access-order</i>). This kind of map is well-suited to 61 * building LRU caches. Invoking the <tt>put</tt> or <tt>get</tt> method 62 * results in an access to the corresponding entry (assuming it exists after 63 * the invocation completes). The <tt>putAll</tt> method generates one entry 64 * access for each mapping in the specified map, in the order that key-value 65 * mappings are provided by the specified map's entry set iterator. <i>No 66 * other methods generate entry accesses.</i> In particular, operations on 67 * collection-views do <i>not</i> affect the order of iteration of the backing 68 * map. 69 * 70 * <p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to 71 * impose a policy for removing stale mappings automatically when new mappings 72 * are added to the map. 73 * 74 * <p>This class provides all of the optional <tt>Map</tt> operations, and 75 * permits null elements. Like <tt>HashMap</tt>, it provides constant-time 76 * performance for the basic operations (<tt>add</tt>, <tt>contains</tt> and 77 * <tt>remove</tt>), assuming the hash function disperses elements 78 * properly among the buckets. Performance is likely to be just slightly 79 * below that of <tt>HashMap</tt>, due to the added expense of maintaining the 80 * linked list, with one exception: Iteration over the collection-views 226 */ 227 public LinkedHashMap(int initialCapacity, 228 float loadFactor, 229 boolean accessOrder) { 230 super(initialCapacity, loadFactor); 231 this.accessOrder = accessOrder; 232 } 233 234 /** 235 * Called by superclass constructors and pseudoconstructors (clone, 236 * readObject) before any entries are inserted into the map. Initializes 237 * the chain. 238 */ 239 @Override 240 void init() { 241 header = new Entry<>(-1, null, null, null); 242 header.before = header.after = header; 243 } 244 245 /** 246 * Returns <tt>true</tt> if this map maps one or more keys to the 247 * specified value. 248 * 249 * @param value value whose presence in this map is to be tested 250 * @return <tt>true</tt> if this map maps one or more keys to the 251 * specified value 252 */ 253 public boolean containsValue(Object value) { 254 // Overridden to take advantage of faster iterator 255 if (value==null) { 256 for (Entry<?,?> e = header.after; e != header; e = e.after) 257 if (e.value==null) 258 return true; 259 } else { 260 for (Entry<?,?> e = header.after; e != header; e = e.after) 261 if (value.equals(e.value)) 262 return true; 263 } 264 return false; 265 } 286 e.recordAccess(this); 287 return e.value; 288 } 289 290 /** 291 * Removes all of the mappings from this map. 292 * The map will be empty after this call returns. 293 */ 294 public void clear() { 295 super.clear(); 296 header.before = header.after = header; 297 } 298 299 /** 300 * LinkedHashMap entry. 301 */ 302 private static class Entry<K,V> extends HashMap.Entry<K,V> { 303 // These fields comprise the doubly linked list used for iteration. 304 Entry<K,V> before, after; 305 306 Entry(int hash, K key, V value, Object next) { 307 super(hash, key, value, next); 308 } 309 310 /** 311 * Removes this entry from the linked list. 312 */ 313 private void remove() { 314 before.after = after; 315 after.before = before; 316 } 317 318 /** 319 * Inserts this entry before the specified existing entry in the list. 320 */ 321 private void addBefore(Entry<K,V> existingEntry) { 322 after = existingEntry; 323 before = existingEntry.before; 324 before.after = this; 325 after.before = this; 326 } 327 328 /** 329 * This method is invoked by the superclass whenever the value 330 * of a pre-existing entry is read by Map.get or modified by Map.put. 331 * If the enclosing Map is access-ordered, it moves the entry 332 * to the end of the list; otherwise, it does nothing. 333 */ 334 void recordAccess(HashMap<K,V> m) { 335 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; 336 if (lm.accessOrder) { 337 lm.modCount++; 338 remove(); 339 addBefore(lm.header); 340 } 341 } 342 343 void recordRemoval(HashMap<K,V> m) { 344 remove(); 345 } 346 } 347 348 private abstract class LinkedHashIterator<T> implements Iterator<T> { 349 Entry<K,V> nextEntry = header.after; 350 Entry<K,V> lastReturned = null; 388 } 389 390 private class ValueIterator extends LinkedHashIterator<V> { 391 public V next() { return nextEntry().value; } 392 } 393 394 private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { 395 public Map.Entry<K,V> next() { return nextEntry(); } 396 } 397 398 // These Overrides alter the behavior of superclass view iterator() methods 399 Iterator<K> newKeyIterator() { return new KeyIterator(); } 400 Iterator<V> newValueIterator() { return new ValueIterator(); } 401 Iterator<Map.Entry<K,V>> newEntryIterator() { return new EntryIterator(); } 402 403 /** 404 * This override alters behavior of superclass put method. It causes newly 405 * allocated entry to get inserted at the end of the linked list and 406 * removes the eldest entry if appropriate. 407 */ 408 @Override 409 void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) { 410 super.addEntry(hash, key, value, bucketIndex, checkIfNeedTree); 411 412 // Remove eldest entry if instructed 413 Entry<K,V> eldest = header.after; 414 if (removeEldestEntry(eldest)) { 415 removeEntryForKey(eldest.key); 416 } 417 } 418 419 /* 420 * Create a new LinkedHashMap.Entry and setup the before/after pointers 421 */ 422 @Override 423 HashMap.Entry<K,V> newEntry(int hash, K key, V value, Object next) { 424 Entry<K,V> newEntry = new Entry<>(hash, key, value, next); 425 newEntry.addBefore(header); 426 return newEntry; 427 } 428 429 /** 430 * Returns <tt>true</tt> if this map should remove its eldest entry. 431 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after 432 * inserting a new entry into the map. It provides the implementor 433 * with the opportunity to remove the eldest entry each time a new one 434 * is added. This is useful if the map represents a cache: it allows 435 * the map to reduce memory consumption by deleting stale entries. 436 * 437 * <p>Sample use: this override will allow the map to grow up to 100 438 * entries and then delete the eldest entry each time a new entry is 439 * added, maintaining a steady state of 100 entries. 440 * <pre> 441 * private static final int MAX_ENTRIES = 100; 442 * 443 * protected boolean removeEldestEntry(Map.Entry eldest) { 444 * return size() > MAX_ENTRIES; 445 * } 446 * </pre> |