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>
|