This class is a Map implementation based on a hashtable, just like its superclass HashMap. It defines no new public methods, and can be used exactly as HashMap is used. What is unique about this Map is that in addition to the hashtable data structure, it also uses a doubly-linked list to connect the keys of the Map into an internal list which defines a predictable iteration order.

You can iterate through the keys or values of a LinkedHashMap by calling enTRySet( ), keySet( ), or values( ) and then obtaining an Iterator for the returned collection, just as you would for a HashMap. When you do this, however, the keys and/or values are returned in a well-defined order rather than the essentially random order provided by a HashMap. The default ordering for LinkedHashMap is the insertion order of the key: the first key inserted into the Map is enumerated first (as is the value associated with it), and the last entry inserted is enumerated last. Note that this order is not affect by re-insertions. That is, if a LinkedHashMap contains a mapping from a key k to a value v1, and you call the put( ) method to map from k to a new value v2, this does not change the insertion order, or the iteration order of the key k. The iteration order of a value in the map is the iteration order of the key with which it is associated.

Insertion order is the default iteration order for this class, but if you instantiate a LinkedHashMap with the three-argument constructor, and pass true for the third argument, then the iteration order will be based on access order: the first key returned by an iterator is the one that was least-recently used in a get( ) or put( ) operation. The last key returned is the one that has been most-recently used. As with insertion order, the values( ) collection is iterated in the order defined by the keys with which those values are associated.

"Access ordering" is particularly useful for implementing "LRU" caches from which the Least-Recently Used elements are periodically purged. To facilitate this use, LinkedHashMap defines the protected removeEldestEntry( ) method. Each time the put( ) method is called (or for each mapping added by putAll( )) the LinkedHashMap calls removeEldestEntry( ) and passes the least-recently used (or first inserted if insertion order is being used) Map.Entry object. If the method returns true, then that entry will be removed from the map. In LinkedHashMap, removeEldestEntry( ) always returns false, and old entries are never automatically removed, but you can override this behavior in a subclass. The decision to remove an old entry might be based on the content of the entry itself, or might more simply be based on the size( ) of the LinkedHashMap. Note that removeEldestEntry( ) need simply return true or false; it should not remove the entry itself.

Figure 16-36. java.util.LinkedHashMap<K,V>

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
// Public Constructors
     public LinkedHashMap( );  
     public LinkedHashMap(int initialCapacity);  
     public LinkedHashMap(Map<? extends K,? extends V> m);  
     public LinkedHashMap(int initialCapacity, float loadFactor);  
     public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder);  
// Methods Implementing Map
     public void clear( );  
     public boolean containsValue(Object value);  
     public V get(Object key);  
// Protected Instance Methods
     protected boolean removeEldestEntry(Map.Entry<K,V> eldest);     constant
}