Table of Contents

  • Summary of LinkedHashMap
  • LinkedHashMap is defined in the JDK
    • Class structure definition
    • Member variable definition
    • Member method definition
    • Basic element Entry
  • Constructor of LinkedHashMap
    • LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)
    • LinkedHashMap(Map<? extends K, ? extends V> m)
    • The init method
  • Data structure of LinkedHashMap
  • Quick access to LinkedHashMap
    • Storage implementation of LinkedHashMap: Put (Key, vlaue)
    • LinkedHashMap expansion operation: resize()
    • Get (Object key)
    • LinkedHashMap Access summary
  • LinkedHashMap and LRU(Least recently used) algorithm
    • Put operation with flag bit accessOrder
    • Get operation with flag bit accessOrder
    • LinkedListMap and LRU summary
  • The LRU algorithm is implemented using LinkedHashMap
  • Analysis of the order principle of LinkedHashMap
  • JDK1.8 changes
  • conclusion

This article has references to a number of quality technology blogs, which can be found at the bottom of the article

Abstract:

A HashMap and a bidirectional linked list are combined to create a LinkedHashMap. Called a LinkedHashMap, it lands on a HashMap, so it is more accurate to say that it is a HashMap that links all Entry nodes into a two-way linked list.

Since LinkedHashMap is a subclass of HashMap, LinkedHashMap naturally has all the features of HashMap. For example, the LinkedHashMap element access process is basically similar to that of HashMap, with a slight difference in implementation details. Of course, this is due to the nature of LinkedHashMap itself, as it maintains an additional two-way linked list to maintain iteration order.

In addition, LinkedHashMap can support LRU algorithm very well. In Section 7, the author realized a structure that can support LRU well based on LinkedHashMap.

Friendly tips:

All the source code for LinkedHashMap in this article is based on JDK 1.6. There may be some differences between JDK versions, but it does not affect our overall understanding of LinkedHashMap data structure, principle and so on. 1.8 changes to LinkedHashMap will be explained later.

Because LinkedHashMap is a subclass of HashMap, it has all the features of HashMap, especially in source sharing. Therefore, before reading this article, it is advisable for readers to have a thorough understanding and review of HashMap, otherwise it is likely to result in half the effort. Refer to my previous article on HashMaps.

Summary of LinkedHashMap

As I mentioned, HashMap is an important member of the Java Collection Framework and one of the most commonly used of the Map family (shown in the figure below). Unfortunately, the HashMap is unordered, meaning that iterating through the HashMap results in elements in a different order than they were originally placed into the HashMap.

This shortcoming of HashMap tends to cause a lot of inconvenience, because there are scenarios where we really need a Map that preserves the insertion order. Fortunately, the JDK solved this problem for us by providing a subclass of HashMap, LinkedHashMap. Although the LinkedHashMap increases the time and space overhead, it ensures the iteration order by maintaining an additional bidirectional linked list.

In particular, the iteration order can be either an insert order or an access order. Therefore, according to the order of the elements in the linked list, linkedhashMaps can be divided into: linkedhashMaps that maintain the insertion order and linkedhashmaps that maintain the access order, where the default implementation of linkedhashMaps is sorted by insertion order.

　　　　　　　　　　　

In essence, a HashMap and a bidirectionally linked list are combined into a LinkedHashMap. The LinkedHashMap has a foothold in a HashMap, so it is more accurate to say that it is a HashMap that links all Entry nodes into a bidirectionally linked list.

In LinkedHashMapMap, all put entries are stored in the hash table as shown in the first figure below, but since it also defines a bidirectional list with head (as shown in the second figure below), for each put Entry, In addition to saving it to its appropriate location in the hash table, it is inserted at the end of the bidirectional list.

More intuitively, the following image nicely captures the original LinkedHashMap: The close cooperation and division of labor between HashMap and bidirectional linked list results in LinkedHashMap. In particular, next is used to maintain the Entry chain in each bucket of the HashMap, and before and After are used to maintain the two-way LinkedHashMap list. Although they are both objects of Entry, they are separate things.

The Entry structure diagram of HashMap and LinkedHashMap is as follows:

In particular, because LinkedHashMap is a subclass of HashMap, LinkedHashMap naturally has all the features of HashMap. For example, the ==LinkedHashMap allows only one Entry key to be Null(multiple entries will be overwritten), but allows multiple entries to be Null. In addition, LinkedHashMap is an asynchronous implementation of Map. In addition, LinkedHashMap can be used to implement the LRU (Least Recently Used) algorithm, which is discussed in particular below.

LinkedHashMap is defined in the JDK

Class structure definition

LinkedHashMap descends from HashMap, which is defined in the JDK as:

public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V> {

    ...
}
Copy the code

Member variable definition

Compared with HashMap, LinkedHashMap adds two attributes to ensure iteration order, namely header and accessOrder (when the value is true, it means iteration in accessOrder; A value of false iterates in the order of insertion.

/** * The head of the doubly linked list. */ private transient Entry<K,V> header; /** * The iteration ordering method for this linked hash map: <tt>true</tt> * for access-order, <tt>false</tt> for insertion-order. * * @serial */ private final boolean accessOrder; // True iterates in access order, false in insert orderCopy the code

Member method definition

As you can see from the figure below, there are no additional methods added to the LinkedHashMap. That is, a LinkedHashMap is roughly the same in operation as a HashMap, only slightly different in implementation details.

Outside the chain picture archiving failure (img – C2vYmjQ7-1567839753833) (static.zybuluo.com/Rico123/nvo…)”

Basic element Entry

LinkedHashMap uses the same hash algorithm as HashMap, but it redefines Entry. Entry in the LinkedHashMap adds two Pointers, before and After, which are used to maintain a list of two-way links. In particular, next is used to maintain the join order of entries in each bucket of the HashMap. Before and after are used to maintain the order of Entry insertion. The source code is as follows:

private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration. Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); }... }Copy the code

Figuratively, the Entry structure of HashMap and LinkedHashMap is shown below:

Constructor of LinkedHashMap

LinkedHashMap provides five constructors, all of which build on the HashMap constructor. Except for the default null parameter constructor, the following constructor contains most of the parameters used by the other constructors.

LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder)

This constructor is intended to construct a LinkedHashMap with a specified iteration order and a specified initial capacity and a specified load factor. The source code is as follows:

/** * Constructs an empty LinkedHashMap instance with the * specified initial capacity, load factor and ordering mode. * * @param initialCapacity the initial capacity * @param loadFactor the load factor * @param accessOrder the ordering mode – true for * access-order, false for insertion-order * @throws IllegalArgumentException if the initial capacity is negative * or the load factor is nonpositive */ public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); // Call the HashMap constructor this.accessOrder = accessOrder; // Default for iteration order}

Initial capacity and load factor are two important parameters that affect the performance of a HashMap. As such, they are two important parameters that affect LinkedHashMap performance. In addition, the LinkedHashMap adds two attributes, header and accessOrder, to ensure the iteration order.

LinkedHashMap(Map<? extends K, ? extends V> m)

This constructor is intended to construct a LinkedHashMap that has the same mapping as the specified Map, with an initial capacity of at least 16 (depending on the size of the specified Map) and a load factor of 0.75, as recommended by the Java Collection Framework specification. The source code is as follows:

/** * Constructs an insertion-ordered <tt>LinkedHashMap</tt> instance with * the same mappings as the specified map. The <tt>LinkedHashMap</tt> * instance is created with a default load factor (0.75) and an initial * capacity sufficient to hold the mappings in the specified map. * * @param m the map whose mappings are to be placed in this map * @throws NullPointerException if the specified map is null */ public LinkedHashMap(Map<? extends K, ? extends V> m) { super(m); // Call the HashMap constructor accessOrder = false; // Default for iteration order}Copy the code

The init method

As you can see from the above five constructors, no matter how a LinkedHashMap is created, the corresponding constructor of the HashMap is called. In fact, no matter which constructor of a HashMap is called, the constructor of a HashMap is initialized at the end by calling an init() method, except that this method is an empty implementation in the HashMap and overridden in LinkedHashMap to initialize the bidirectly-linked list it maintains. For example, the source code for the null HashMap constructor and init method is as follows:

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
    table = new Entry[DEFAULT_INITIAL_CAPACITY];
    init();
}
Copy the code

/** * Initialization hook for subclasses. This method is called * in all constructors and pseudo-constructors (clone, readObject) * after HashMap has been initialized but before any entries have * been inserted. (In the absence of this method, readObject would * require explicit knowledge of subclasses.) */ void init() { }

In LinkedHashMap, it overrides the init method to initialize the bidirectional list as follows:

/** * Called by superclass constructors and pseudoconstructors (clone, * readObject) before any entries are inserted into the map. Initializes * the chain. */ void init() { header = new Entry<K,V>(-1, null, null, null); header.before = header.after = header; }

Thus, we unknowingly initialize the bidirectional linked list as we create the LinkedHashMap.

Data structure of LinkedHashMap

In essence, LinkedHashMap = HashMap + bidirectional linked list, that is, HashMap and bidirectional linked list combined into one is LinkedHashMap.

Alternatively, the LinkedHashMap adds two lines (before and after Pointers) between any two nodes of the HashMap without making any changes to the HashMap, making them a bidirectional list.

In LinkedHashMapMap, all put entries are stored in the HashMap, but since it defines an empty bidirectional list with head as a header, it is inserted at the end of the bidirectional list for each put Entry.

　　　　　　　　　　　　

Quick access to LinkedHashMap

We know that the two most common operations in a HashMap are PUT (Key,Value) and get(Key). Again, these are the two most commonly used operations in LinkedHashMap.

As for the PUT (Key,Value) method, LinkedHashMap completely inherits the Put (Key,Value) method of HashMap, but overwrites the recordAccess and addEntry methods called by put(Key,Value). For the get(Key) method, LinkedHashMap overrides it directly.

Let’s look at the access implementation of LinkedHashMap with JDK source code.

Storage implementation of LinkedHashMap: Put (Key, vlaue)

As mentioned above, LinkedHashMap does not make any direct changes to the put(key,vlaue) method, but completely inherited the Put (key, Value) method from HashMap.

Public V put(K key, V value) {// putForNullKey is called when the key is null. If (key == NULL) return putForNullKey(value); Int hash = hash(key.hashcode ()); Int I = indexFor(hash, table.length); int I = indexFor(hash, table.length); For (Entry<K,V> e = table[I]; for (Entry<K,V> e = table[I]; e ! = null; e = e.next) { Object k; // Determine if there is a mapping on the chain with the same hash value and the same key value. If there is, overwrite value directly. And returns the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); // LinkedHashMap overwrites Entry's recordAccess method -- (1) return oldValue; // return the old value}} modCount++; // If the Map does not exist in the original Map, add the Map to the header addEntry(hash, key, value, I) of the chain. // LinkedHashMap overwrites HashMap createEntry method ---- (2) return null; }Copy the code

The above source code reflects how LinkedHashMap and HashMap save data. In particular, in LinkedHashMap, it overrides the addEntry method and Entry’s recordAccess method. Let’s compare the implementation of the addEntry method for LinkedHashMap and HashMap:

/** * This override alters behavior of superclass put method. It causes newly * allocated entry to get inserted at the End of the linked list and * post the eldest entry if appropriate. * * LinkedHashMap addEntry method */ void addEntry(int Hash, K key, V value, int bucketIndex) {// Create a new Entry and insert it into the LinkedHashMap createEntry(Hash, Key, value, bucketIndex); > <K,V> younger = header.after; // The createEntry method in the HashMap is overworked; // The first valid node in the list is the least recently used node; // Remove the least recently used node if necessary, depending on the override of removeEldestEntry, which defaults to false and does nothing by default. if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else {if (size >= threshold) resize(2 * table.length); }} -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- I'm line -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - / * * * Adds a new entry with the specified key, value and hash code to * the specified bucket. It is the responsibility of this * method to resize the table if Appropriate. * * Subclass overrides this to alter the behavior of put method. * * HashMap addEntry method */ void AddEntry (int hash, K key, V value, int bucketIndex) {// Get the Entry of bucketIndex. Entry<K,V> e = table[bucketIndex]; // Add the newly created Entry to the bucketIndex index and make the new Entry point to the original Entry. Table [bucketIndex] = New Entry<K,V>(hash, key, value, e); If (size++ >= threshold) resize(2 * table.length); }Copy the code

Since LinkedHashMap itself maintains the order of inserts, it can be used for caching, and lines 14-19 are used to support the LRU algorithm, so don’t worry about it here. Additionally, in the addEntry method of LinkedHashMap, it overrides the createEntry method in HashMap. Let’s look at the createEntry method next:

Void createEntry(int hash, K key, V value, int bucketIndex) {// Insert Entry into the hash table, Entry<K,V> old = table[bucketIndex]; // Create a new Entry and chain it to the head of the bucket list. Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; // Every time an Entry is inserted into the hash table, it is inserted at the end of the bidirectional list. // This iterates through the elements in the order in which the Entry was inserted into the LinkedHashMap. The newly put Entry is the most recently accessed Entry. Putting it at the end of the linked list also conforms to the implementation of the LRU algorithm. size++; }Copy the code

As you can see from the source code above, when inserting a new Entry into the hash table in the LinkedHashMap, it is also linked to the two-way list via the Entry addBefore method. Where, the addBefore method is essentially a bidirectional linked list insert operation, its source code is as follows:

// In a bidirectional list, insert the current Entry before existingEntry(header) private void addBefore(Entry<K,V> existingEntry) {after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }Copy the code

So far, we’ve looked at the entire process of putting a key-value pair in a LinkedHashMap. In general, in contrast to a HashMap, a LinkedHashMap adds a key-value pair to a hash table while also linking it to the bidirectional list it maintains to set the iteration order.

LinkedHashMap expansion operation: resize()

In HashMap, we know that as the number of elements in HashMap increases, the probability of collisions will increase and the length of subchains generated will become longer, which is bound to affect the access speed of HashMap.

To ensure the efficiency of HashMap, the system must expand at a critical point, where the number of elements in HashMap is equal to threshold (table array length * load factor).

I have to say, however, that scaling is a time-consuming process, because it requires recalculating the positions of these elements in the new TABLE array and copying them. Therefore, if we can predict the number of elements in a HashMap in advance, the preset number of elements when constructing a HashMap can effectively improve the performance of the HashMap.

The same problem applies to LinkedHashMap, which is essentially a HashMap, except that it also links all Entry nodes into a two-way list. LinkedHashMap completely inherits the HashMap resize() method, but overrides the Transfer method it calls. Resize (); resize();

void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; // If oldCapacity has reached the maximum value, Set threshold to integer. MAX_VALUE if (oldCapacity == MAXIMUM_CAPACITY) {threshold = integer.max_value; return; } // Otherwise, create a larger array Entry[] newTable = new Entry[newCapacity]; // Transfer (newTable) each Entry into the new array; //LinkedHashMap overwrites the transfer method it calls table = newTable; threshold = (int)(newCapacity * loadFactor); // Reset threshold}Copy the code

As you can see from the above code, the core of the Map expansion operation is rehash. Rehash is the process of recalculating the position of the elements in the original HashMap in the new table array and copying them. In view of performance and LinkedHashMap’s own characteristics, LinkedHashMap rewrites the transfer method, the source code is as follows:

/** * Transfers all entries to new table array. This method is called * by superclass resize. It is overridden for performance, as it is * faster to iterate using our linked list. */ void transfer(HashMap.Entry[] newTable) { int newCapacity = newTable.length; For (Entry<K,V> e = header.after; for (Entry<K,V> e = header.after; e ! = header; e = e.after) { int index = indexFor(e.hash, newCapacity); E.next = newTable[index]; // Count the bucket to which each Entry belongs. newTable[index] = e; }}Copy the code

As shown in the source code above, LinkedHashMap easily implements rehashing with self-maintained bidirectional lists.

Get (Object key)

Reading the LinkedHashMap is relatively simple compared to storing it. LinkedHashMap rewrite HashMap get method, source code is as follows:

Public V get(Object key) {// Get the corresponding Entry according to the key. If there is no such Entry, null Entry<K,V> e = (Entry<K,V>)getEntry(key); If (e == null) // If no such Entry exists, return NULL; e.recordAccess(this); return e.value; } /** * Returns the entry associated with the specified key in the * HashMap. Returns null if the HashMap contains no Mapping * for the key. * * Final Entry<K,V> getEntry(Object key) {if (size == 0) {return null; } int hash = (key == null) ? 0 : hash(key); for (Entry<K,V> e = table[indexFor(hash, table.length)]; e ! = null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || (key ! = null && key.equals(k)))) return e; } return null; }Copy the code

In the Get method of the LinkedHashMap, the Entry object is obtained through the getEntry method in the HashMap. Note the recordAccess method here, which does nothing if the list elements are sorted by insertion order; Move E to the end of the list if the list is sorted by the order in which the elements are accessed, which I will discuss later.

Similarly, if the return value is NULL after calling the get(Object key) method of the LinkedHashMap, the following two possibilities exist:

The value of this key is NULL. The key does not exist in the HashMap.

LinkedHashMap Access summary

The access process of LinkedHashMap is basically similar to that of HashMap, except that the implementation is slightly different in detail. This is due to the nature of LinkedHashMap itself, because it maintains an additional two-way list to maintain the iteration order.

Although LinkedHashMap fully inherits the HashMap PUT operation, it still makes some adjustments in details. For example, when inserting new entries into the hash table, It is also linked to the bidirectional list via Entry’s addBefore method.

In terms of capacity expansion operation, although LinkedHashMap completely inherits the resize operation of HashMap, in view of performance and characteristics of LinkedHashMap, LinkedHashMap rewrites the transfer method. In the read operation, LinkedHashMap overrides the get method in HashMap and obtains the Entry object through the getEntry method in HashMap. On this basis, the value corresponding to the specified key is further obtained.

LinkedHashMap and LRU(Least recently used) algorithm

At this point, we have analyzed the access implementation of LinkedHashMap, which is roughly the same as HashMap. One of the biggest differences between LinkedHashMap and HashMap is that the former is ordered while the latter is unordered. To do this, we add two attributes to the LinkedHashMap to ensure order: header and accessOrder.

As we know, header is the head of the bidirectional linked list maintained by LinkedHashMap, and accessOrder is used to determine the exact iteration order. In fact, the function of the accessOrder flag bit is not as simple as we describe, so let’s take a closer look at the wave ~

We know that when the accessOrder flag bit is true, it means that the elements in the bidirectional list are listed in the order they were accessed. As you can see, even though the entries are inserted into the list in the order they were put into the LinkedHashMap, But both the PUT and get methods call the recordAccess method (the PUT method is called if the key is the same).

The recordAccess method determines whether accessOrder is true, and if so, it moves the currently accessed Entry (put Entry or get Entry) to the end of the bidirectional list. It calls createEntry, which also places the newly inserted element at the end of the bidirectional list, in both the order of insertion and the order of access, because that Entry was also accessed.)

When the value of accessOrder is false, it indicates that the elements in the bidirectional list are sorted in the order in which the Entry is inserted into the LinkedHashMap. That is, each Entry put into the LinkedHashMap is placed at the end of the bidirectional list. In this way, when traversing the bidirectional list, The order of Entry output is the same as the order of insertion, which is the default bidirectional list storage order.

Therefore, when the flag bit accessOrder is false, the recordAccess method is also called, but nothing is done.

Put operation with flag bit accessOrder

Public V put(K key, V value) {// If the key is null, add the key/value pair to table[0]. if (key == null) return putForNullKey(value); // If the key is not null, the hash value of the key is calculated and added to the linked list corresponding to the hash value. int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); for (Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k; / / if the key already exists, the new value to replace the old value if (e.h ash = = hash && ((k = e.k ey) = = key | | key. Equals (k))) {V oldValue = e.v alue. e.value = value; e.recordAccess(this); return oldValue; // add key/value to table modCount++ if key does not exist; // Add key/value pairs to table[I] addEntry(hash, key, value, I); return null; }Copy the code

The Entry recordAccess method is called when the Entry key already exists in the hash table. When the key does not exist, the addEntry method is called to insert the new Entry into the head of the single-linked list of the corresponding bucket. Let’s start with the recordAccess method:

/** * This method is invoked by the superclass whenever the value * of a pre-existing entry is read by Map.get or modified by Map.set. * If the enclosing Map is access-ordered, it moves the entry * to the end of the list; otherwise, it does nothing. */ void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; // If the list is sorted by access order, the currently accessed Entry is moved to the end of the bidirectional circular list, and if the list is sorted by insertion order, nothing is done. if (lm.accessOrder) { lm.modCount++; // Remove Entry (); // Insert the currently accessed Entry to the end of the list addBefore(lm.header); }}Copy the code

LinkedHashMap overrides the recordAccess method in HashMap (null in HashMap), which is called when the put method of the parent class is found to already exist; This method is also called when you call your own GET method.

This method provides an implementation of the LRU algorithm, which puts the most recently used Entry at the end of a bidirectional circular list. That is, when accessOrder is true, both the GET and PUT methods call the recordAccess method to move the most recently used Entry to the end of the two-way list; When accessOrder is false, you can see from the source that the recordAccess method does nothing. Let’s work backwards and look at the addEntry method again:

/** * This override alters behavior of superclass put method. It causes newly * allocated entry to get inserted at the End of the linked list and * post the eldest entry if appropriate. * * LinkedHashMap addEntry method */ void addEntry(int hash, K key, V value, int bucketIndex) {

CreateEntry (Hash, Key, Value, bucketIndex); // Create a new Entry and insert it into the LinkedHashMap. > <K,V> younger = header.after; // The createEntry method in the HashMap is overworked; // The first valid node in the list is the least recently used node; // Remove the least recently used node if necessary, depending on the override of removeEldestEntry, which defaults to false and does nothing by default. if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); } else {if (size >= threshold) resize(2 * table.length); }} void createEntry(int hash, K key, V value, int bucketIndex) {// Insert Entry into the hash table, Entry<K,V> old = table[bucketIndex]; // Create a new Entry and chain it to the head of the bucket list. Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e; // Every time an Entry is inserted into the hash table, it is inserted at the end of the bidirectional list. // This iterates through the elements in the order in which the Entry was inserted into the LinkedHashMap. The newly put Entry is the most recently accessed Entry. Putting it at the end of the linked list also conforms to the implementation of the LRU algorithm. size++; }Copy the code

The new Entry is also linked to the single list in the bucket in the table, but as you can see from createEntry, the new Entry is also inserted to the end of the two-way list. From the perspective of insertion order, new entries inserted into the end of the bidirectional list can be iterated according to the order of insertion. From the perspective of access order, the newly put Entry is the most recently accessed Entry and should also be placed at the end of the bidirectional list. The addEntry method also calls the removeEldestEntry method. The source code of this method is as follows:

/** * Returns <tt>true</tt> if this map should remove its eldest entry. * This method is invoked by <tt>put</tt> and <tt>putAll</tt> after * inserting a new entry into the map. It provides the implementor * with the opportunity to remove  the eldest entry each time a new one * is added. This is useful if the map represents a cache: it allows * the map to reduce memory consumption by deleting stale entries. * * <p>Sample use: this override will allow the map to grow up to 100 * entries and then delete the eldest entry each time a new entry is *  added, maintaining a steady state of 100 entries. * <pre> * private static final int MAX_ENTRIES = 100; * * protected boolean removeEldestEntry(Map.Entry eldest) { * return size() > MAX_ENTRIES; * } * </pre> * * <p>This method typically does not modify the map in any way, * instead allowing the map to modify itself as directed by its * return value. It <i>is</i> permitted for this method to  modify * the map directly, but if it does so, it <i>must</i> return * <tt>false</tt> (indicating that the map should not attempt any * further modification). The effects of returning <tt>true</tt> * after modifying the map from within this method are unspecified. * * <p>This implementation merely returns <tt>false</tt> (so that this * map acts like a normal map - the eldest element is never removed). * * @param eldest The least recently inserted entry in the map, or if * this is an access-ordered map, the least recently accessed * entry. This is the entry that will be removed it this * method returns <tt>true</tt>. If the map was empty prior * to the <tt>put</tt> or <tt>putAll</tt> invocation resulting * in this invocation, this will be the entry that was just * inserted; in other words, if the map contains a single * entry, the eldest entry is also the newest. * @return <tt>true</tt> if the eldest entry should be removed * from the map; <tt>false</tt> if it should be retained. */ protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }Copy the code

}

This method is intended to be overridden, and is generally overridden if the LRU algorithm is implemented with LinkedHashmap. For example, you can overwrite this method to return true if the set memory is full, so that when putEntry in LinkedHashMap is called again, the least recently used node (the one after the header) is removed from the addEntry method. In Section 7, I rewrite this method and implement a real LRU structure.

Get operation with flag bit accessOrder

Public V get(Object key) {// Get the corresponding Entry according to the key. If there is no such Entry, null Entry<K,V> e = (Entry<K,V>)getEntry(key); If (e == null) // If no such Entry exists, return NULL; e.recordAccess(this); return e.value; }Copy the code

The recordAccess method is also called when a read is performed in a LinkedHashMap. The above author has expressed very clearly, this does not repeat.

LinkedListMap and LRU summary

A necessary prerequisite for implementing LRU using LinkedHashMap is to set the accessOrder flag bit to true to enable the mode of sorting by accessOrder. As we can see, both the PUT and get methods cause the target Entry to be the most recently accessed Entry, so that Entry is added to the end of the two-way list: the GET method is implemented by calling the recordAccess method;

The put method is also implemented by calling the recordAccess method when overwriting an existing key, or by inserting a new Entry through the addBefore method in createEntry. This puts the most recently used Entry at the end of the two-way list. After multiple operations, the Entry at the front of the bidirectional list is not used recently. In this case, when the number of nodes is full, delete the Entry at the front (the Entry after the head) because it is the least used Entry.

The LRU algorithm is implemented using LinkedHashMap

As shown below, the author uses LinkedHashMap to implement a data structure that complies with LRU algorithm. This structure can cache up to 6 elements, but when there are more than 6 elements, it will automatically delete the most recent and longest unused elements, as shown below:

public class LRU<K,V> extends LinkedHashMap<K, V> implements Map<K, V>{ private static final long serialVersionUID = 1L;  public LRU(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor, accessOrder); } /** * @description overwrites the removeEldestEntry method in the LinkedHashMap. * Remove the least frequently used element * @author Rico * @created May 12, 2017 11:32:51 am * @param Eldest * @return * @see java.util.LinkedHashMap#removeEldestEntry(java.util.Map.Entry) */ @Override protected boolean removeEldestEntry(java.util.Map.Entry<K, V> eldest) { // TODO Auto-generated method stub if(size() > 6){ return true; } return false; } public static void main(String[] args) {LRU<Character, Integer> LRU = new LRU<Character, Integer>(16, 0.75f, true); String s = "abcdefghijkl"; for (int i = 0; i < s.length(); i++) { lru.put(s.charAt(i), i); } system.out. println("LRU Entry with key h = "+ lru.get('h')); System.out.println("LRU size: "+ lru.size()); System.out.println("LRU: "+ LRU); }}Copy the code

The following is the result of the program:

Analysis of the order principle of LinkedHashMap

As mentioned above, the LinkedHashMap adds two attributes, header and accessOrder, to ensure the iteration order. We need to rewrite the iterator of the HashMap. The source code is as follows:

private abstract class LinkedHashIterator<T> implements Iterator<T> { Entry<K,V> nextEntry = header.after; Entry<K,V> lastReturned = null; /** * The modCount value that the iterator believes that the backing * List should have. If this expectation is violated, the iterator * has detected concurrent modification. */ int expectedModCount = modCount; Public Boolean hasNext() {return nextEntry! = header; } public void remove() { if (lastReturned == null) throw new IllegalStateException(); if (modCount ! = expectedModCount) throw new ConcurrentModificationException(); LinkedHashMap.this.remove(lastReturned.key); lastReturned = null; expectedModCount = modCount; } Entry<K,V> nextEntry() {// Iterate over each node of the bidirectional list if (modCount! = expectedModCount) throw new ConcurrentModificationException(); if (nextEntry == header) throw new NoSuchElementException(); Entry<K,V> e = lastReturned = nextEntry; nextEntry = e.after; return e; }} // Key iterator, KeySet private class KeyIterator extends LinkedHashIterator<K> { public K next() { return nextEntry().getKey(); }} // Value iterator, Values(Collection) private class ValueIterator extends LinkedHashIterator<V> { public V next() { return nextEntry().value; }} // Entry iterator, EntrySet private class EntryIterator extends LinkedHashIterator<Map.Entry<K,V>> { public Map.Entry<K,V> next() { return nextEntry(); }}Copy the code

From the code above, we know that LinkedHashMap overrides the HashMap iterator, which iterates over output using the bidirectional linked list it maintains.

JDK1.8 changes

The original article is based on the JDK1.6 implementation, but is actually modified by JDK1.8. First, it removes methods like AddEntry, Createenrty, etc. (in fact, changes to the HashMap have affected it).

Linkedhashmap also uses most of the add, delete, change and query methods of HashMaps. The new version of LinkedhashMap implements LRU primarily by overwriting several methods built into HashMap.

Hashmap does not provide an implementation:

 void afterNodeAccess(Node<K,V> p) { }
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }
Copy the code

Implementation of LinkedhashMap:

Handles the situation after the element has been accessed

void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) ! = e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a ! = null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; }}Copy the code

Handles the situation after the element is inserted

void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) ! = null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); }Copy the code

Handles the case after the element has been deleted

void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }}Copy the code

In addition, the hashMap of 1.8 will automatically turn into a red-black tree when the length of the linked list exceeds 8, and the elements in the linked list will be inserted in order. You can customize the comparator to define the insertion order of nodes.

1.8 linkedhashMap also uses this feature. When it becomes a red-black tree, the nodes are inserted in the same order as the red-black tree. The bidirectional linked list is not changed, but the original hashmap’s linked list is changed into a red-black tree.

conclusion

In this paper, from the data structure of LinkedhashMap, and source code analysis, to the LRU cache implementation, a more in-depth analysis of the underlying principle of LinkedhashMap. The following points are summarized:

1 LinkedhashMap Connects all nodes into a bidirectional linked list based on the array plus linked list structure of hashMap.

2 When accessOrder is false, new elements are not added to the list when put is used, and elements are not added to the end of the list when get is used.

3 When accessOrder is true, new elements added using put will be placed at the end of the list if they encounter hash conflicts and are replaced with elements with the same key. When the number of elements exceeds the upper limit and removeEldestEntry returns true, Delete the earliest element directly for new element insertion. If there are no conflicts, it goes to the end of the list. When you use the get method, you put the element you get at the end of the bidirectional list.

4 The expansion of LinkedhashMap is more convenient than that of HashMap, because HashMap requires reverse insertion and linking of each element of the original linked list into the new array, while linkedhashMap elements are all connected to a linked list, which can be directly iterated and then inserted.

5 The removeEldestEntry method of linkedhashMap returns false by default. It is important to implement LRU by removing the oldest unaccessed element when the collection is full. In linkedhashMap, this element is the one to which the header pointer points. LRU can be directly implemented to inherit the LinkedhashMap and rewrite the removeEldestEntry method to set the cache size. LRUCache is implemented in the JDK and can be used directly.

Refer to the article

cmsblogs.com/?p=176

www.jianshu.com/p/8f4f58b4b…

Blog.csdn.net/wang_8101/a…

www.cnblogs.com/create-and-…

www.cnblogs.com/ganchuanpu/…