53 * copies it, and later returns results whose order is determined by that of |
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 |
54 * the copy. (Clients generally appreciate having things returned in the same |
55 * order they were presented.) |
55 * order they were presented.) |
56 * |
56 * |
57 * <p>A special {@link #LinkedHashMap(int,float,boolean) constructor} is |
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 |
58 * provided to create a <tt>LinkedHashMap</tt> whose order of iteration is the |
59 * in which its entries were last accessed, from least-recently accessed to |
59 * order in which its entries were last accessed, from least-recently accessed |
60 * most-recently (<i>access-order</i>). This kind of map is well-suited to |
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 |
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 |
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 |
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 |
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 |
65 * mappings are provided by the specified map's entry set iterator. <i>No |
241 header = new Entry<>(-1, null, null, null); |
241 header = new Entry<>(-1, null, null, null); |
242 header.before = header.after = header; |
242 header.before = header.after = header; |
243 } |
243 } |
244 |
244 |
245 /** |
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 |
246 * Returns <tt>true</tt> if this map maps one or more keys to the |
264 * specified value. |
247 * specified value. |
265 * |
248 * |
266 * @param value value whose presence in this map is to be tested |
249 * @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 |
250 * @return <tt>true</tt> if this map maps one or more keys to the |
318 */ |
301 */ |
319 private static class Entry<K,V> extends HashMap.Entry<K,V> { |
302 private static class Entry<K,V> extends HashMap.Entry<K,V> { |
320 // These fields comprise the doubly linked list used for iteration. |
303 // These fields comprise the doubly linked list used for iteration. |
321 Entry<K,V> before, after; |
304 Entry<K,V> before, after; |
322 |
305 |
323 Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { |
306 Entry(int hash, K key, V value, Object next) { |
324 super(hash, key, value, next); |
307 super(hash, key, value, next); |
325 } |
308 } |
326 |
309 |
327 /** |
310 /** |
328 * Removes this entry from the linked list. |
311 * Removes this entry from the linked list. |
342 after.before = this; |
325 after.before = this; |
343 } |
326 } |
344 |
327 |
345 /** |
328 /** |
346 * This method is invoked by the superclass whenever the value |
329 * 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. |
330 * of a pre-existing entry is read by Map.get or modified by Map.put. |
348 * If the enclosing Map is access-ordered, it moves the entry |
331 * If the enclosing Map is access-ordered, it moves the entry |
349 * to the end of the list; otherwise, it does nothing. |
332 * to the end of the list; otherwise, it does nothing. |
350 */ |
333 */ |
351 void recordAccess(HashMap<K,V> m) { |
334 void recordAccess(HashMap<K,V> m) { |
352 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; |
335 LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; |
420 /** |
403 /** |
421 * This override alters behavior of superclass put method. It causes newly |
404 * 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 |
405 * allocated entry to get inserted at the end of the linked list and |
423 * removes the eldest entry if appropriate. |
406 * removes the eldest entry if appropriate. |
424 */ |
407 */ |
425 void addEntry(int hash, K key, V value, int bucketIndex) { |
408 @Override |
426 super.addEntry(hash, key, value, bucketIndex); |
409 void addEntry(int hash, K key, V value, int bucketIndex, boolean checkIfNeedTree) { |
|
410 super.addEntry(hash, key, value, bucketIndex, checkIfNeedTree); |
427 |
411 |
428 // Remove eldest entry if instructed |
412 // Remove eldest entry if instructed |
429 Entry<K,V> eldest = header.after; |
413 Entry<K,V> eldest = header.after; |
430 if (removeEldestEntry(eldest)) { |
414 if (removeEldestEntry(eldest)) { |
431 removeEntryForKey(eldest.key); |
415 removeEntryForKey(eldest.key); |
432 } |
416 } |
433 } |
417 } |
434 |
418 |
435 /** |
419 /* |
436 * This override differs from addEntry in that it doesn't resize the |
420 * Create a new LinkedHashMap.Entry and setup the before/after pointers |
437 * table or remove the eldest entry. |
421 */ |
438 */ |
422 @Override |
439 void createEntry(int hash, K key, V value, int bucketIndex) { |
423 HashMap.Entry<K,V> newEntry(int hash, K key, V value, Object next) { |
440 @SuppressWarnings("unchecked") |
424 Entry<K,V> newEntry = new Entry<>(hash, key, value, next); |
441 HashMap.Entry<K,V> old = (HashMap.Entry<K,V>)table[bucketIndex]; |
425 newEntry.addBefore(header); |
442 Entry<K,V> e = new Entry<>(hash, key, value, old); |
426 return newEntry; |
443 table[bucketIndex] = e; |
|
444 e.addBefore(header); |
|
445 size++; |
|
446 } |
427 } |
447 |
428 |
448 /** |
429 /** |
449 * Returns <tt>true</tt> if this map should remove its eldest entry. |
430 * 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 |
431 * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after |