JAVA COLLECTIONS source
1. What is LinkedHashMap
- The underlying layer uses hash tables and bidirectional linked lists to implement an iteratively ordered, asynchronous HashMap
- Added bidirectional lists that maintain order for all elements (so non-traversal performance may be lower than HashMap)
- Contains two sorts: access order and insert order (default)
- Access order facilitates LRU(least recently accessed)
- The traversal speed is only related to the total amount of elements (size), and has nothing to do with capacity
- This version is JDK1.7,
JDK1.8 is working overtime
2. Data structure of LinkedHashMap
- The class definition
/ * ** Make full use of 'polymorphism' in exactly the same way that HashMap manipulates data* /public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
- Important global variable
/ * * * The head of the doubly linked list.* Add a bidirectional list to maintain all elements for sorting (header is the list header); Entry is the private static inner class implementation of LinkedHashMap* /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.* True: Access order (most recently accessed elements moved to the end of the list)* This value is false: insert order (first in first, then back)* /private final boolean accessOrder;
- The constructor
/ * ** 1. Reuse the HashMap constructor directly* 2. Default insertion order (first in first, then back)* /public LinkedHashMap(int initialCapacity, float loadFactor) { super(initialCapacity, loadFactor); accessOrder = false;}/ * ** @param accessOrder false: Insert order; True: Access order (most recently accessed elements moved to the end of the list)* /public LinkedHashMap(int initialCapacity, float loadFactor,boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder;}
- Init method parsing
/ * * * Called by superclass constructors and pseudoconstructors (clone,readObject) * before any entries are inserted into the map. Initializes the chain.* This method follows the template method pattern and has no meaning in the implementation of HashMap. It is only provided to subclass implementations for relevant initialization calls* LinkedHashMap initializes the header* /@Overridevoid init() { header = new Entry<>(-1, null, null, null); header.before = header.after = header;}
- Assuming the header address is 0x00000000, the header after init should look like this:
- Entry of LinkedHashMap
/ * * * LinkedHashMap entry.* /private static class Entry<K,V> extends HashMap.Entry<K,V> { // These fields comprise the doubly linked list used for iteration.// Before points to the previous entry, and after points to the next entry to form a bidirectional list and achieve order// Iterate directly along the bidirectional linked list, so the iteration speed is only related to the total number of elements (size), and has nothing to do with capacity Entry<K,V> before, after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); }/ * * * Removes this entry from the linked list.* / private void remove() { before.after = after; after.before = before; }/ * * * Inserts this entry before the specified existing entry in the list.* The new entry is inserted before the header reference, so that the new entry becomes the last element in the bidirectional list* / private void addBefore(Entry<K,V> existingEntry) {// existingEntry=header after = existingEntry; before = existingEntry.before; before.after = this; after.before = this; }/ * * * 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 (lm.accessOrder) { lm.modCount++; remove(); addBefore(lm.header); } }// Template method void recordRemoval(HashMap<K,V> m) { remove(); }}
3. Iteration sort instance
- But before we do that, let’s give you an intuition of the difference between these two kinds of sorting
- Insertion sort
LinkedHashMap<Integer,String> linkedHashMap = new LinkedHashMap<Integer,String>();LinkedHashMap. Put (1," linkedHashMap ");LinkedHashMap. Put (2," linkedHashMap ");LinkedHashMap. Put (3," Sasaki ");LinkedHashMap. Put (4," Ishihara Rimi ");LinkedHashMap. Put (5," Hkubei Mashi "); Iterator iterator = linkedHashMap.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry entry = (Map.Entry) iterator.next(); System.out.println(entry.getKey() + "=" + entry.getValue()); }
- As shown in the figure, insert in order (first in first, then back)
- Note: Header is always null, but before and after have been changed (bidirectional lists are in effect)
- The before of the header points to the element at the end of the chain (combined with after to form a two-way loop)
- Header after points to the header element (minus the header)
- Access to sort
// Note: accessOrder = true is required for access sort to workLinkedHashMap<Integer,String> linkedHashMap = new LinkedHashMap<Integer,String>(16,0.75f,true);LinkedHashMap. Put (1," linkedHashMap ");LinkedHashMap. Put (2," linkedHashMap ");LinkedHashMap. Put (3," Sasaki ");LinkedHashMap. Put (4," Ishihara Rimi ");LinkedHashMap. Put (5," Hkubei Mashi ");// Access begins linkedHashMap.get(3); linkedHashMap.get(1); Iterator iterator = linkedHashMap.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry entry = (Map.Entry) iterator.next(); System.out.println(entry.getKey() + "=" + entry.getValue()); }
- As shown, in order of access (most recently accessed elements moved to the end of the list)
- The before of the header points to the element at the end of the chain
- The after of the header points to the header element
4. Storage of LinkedHashMap
-
There is one important and confusing point to emphasize before analyzing it (to help you better understand the meaning of the combination of LinkedList and HashMap)
- From the perspective of the table, a new entry needs to be inserted into the corresponding bucket. When a hash conflict occurs, the new entry is inserted into the head of the conflict list using the header interpolation method
- From the header’s perspective, the new entry needs to be inserted at the end of the bidirectional list (
3. Sort examplesUse this Angle to describe); The use of bidirectional lists is mainly for fast ordered iteration
-
Put method parsing
/ * ** LinkedHashMap does not override the put method of its parent 'HashMap' (so don't be surprised if you can't find LinkedHashMap's put method)* But overrides the child method called by the put method of the parent class HashMap to add a bidirectional list implementation* Override submethods: recordAccess(), addEntry(), createEntry()* /public V put(K key, V value) { if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length);for (Entry<K,V> e = table[i]; e ! = null; e = e.next) { Object k; if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value;e.recordAccess(this); //LinkedHashMap Entry overrides the recordAccess method return oldValue; } } modCount++;addEntry(hash, key, value, i); //LinkedHashMap overrides the recordAccess method return null;}
- RecordAccess method resolution
/ * ** Record the access order* /void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;// If we define the iteration order of LinkedHashMap as access order,// Deletes the element from the previous position and adds the latest accessed element to the list header if (lm.accessOrder) {lm.modCount++; // Note: Structural changes will make the modCount count +1 for fail-fastremove(); // Change the list before and after references to ensure orderlinessaddBefore(lm.header); // Add the latest accessed element to the list header }}
- AddEntry method parsing
void addEntry(int hash, K key, V value, int bucketIndex) {// Call the create method to add the new elements to the map as a bidirectional linked list createEntry(hash, key, value, bucketIndex);// Remove the policy definition of the least recently used element Entry<K,V> eldest = header.after;If (removeEldestEntry(Younger)) {// This method returns false by default, which means that LinkedHashMap does not actively delete "expired" elementsremoveEntryForKey(eldest.key); // Call removeEntryForKey() directly from the parent HashMap class } else {If (size >= threshold)// If the threshold is exceeded, resize is executedresize(2 * table.length); // Call the resize method of the parent HashMap directly, doubling the capacity }}
- CreateEntry method parsing
void createEntry(int hash, K key, V value, int bucketIndex) { HashMap.Entry<K,V> old = table[bucketIndex]; Entry<K,V> e = new Entry<K,V>(hash, key, value, old); table[bucketIndex] = e;// Add elements to a hash, bidirectional list e.addBefore(header); size++;}
- Get method parsing
/ * ** Records the access order, adding the most recently accessed element to the head of the bidirectionally linked list and removing it from its original position* List addition and deletion operations are constant* /public V get(Object key) { // Call the getEntry() method of the parent HashMap to get the element to look for Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) return null; // Record the access order e.recordAccess(this); return e.value; }
5. Remove LinkedHashMap
- RemoveEntryForKey method resolution
/ * ** Instead of overwriting removeEntryForKey, LinkedHashMap subtly implements the method using the template method pattern* The following is an implementation of the removeEntryForKey method for HashMap* /final Entry<K,V> removeEntryForKey(Object key) { int hash = (key == null) ? 0 : hash(key);int i = indexFor(hash, table.length); // hash&(table.length-1)Entry<K,V> prev = table[i]; // Get the conflicting linked list Entry<K,V> e = prev;while (e ! = null) {// Iterate over the conflicting linked list Entry<K,V> next = e.next; Object k; if (e.hash == hash &&((k = e.key) == key || (key ! = null && key.equals(k)))) {// Find the entry to delete modCount++; size--;// 1. Delete e from the conflict list for the corresponding bucket if (prev == e) table[i] = next; else prev.next = next;// 2. Delete e from the HashMap as e.recordremoVal (this)Before. After = after; after.before = before; e.recordRemoval(this); return e; } prev = e; e = next; } return e;}/ * ** Delete implementation of LinkedHashMap* /void recordRemoval(HashMap<K,V> m) { remove();}/ * ** When the remove operation is performed inside entry, the elements at the previous positions are deleted by changing the front and back points of the linked list to ensure the order of iteration* /private void remove() { before.after = after; after.before = before;}
-
Remove method parsing
- From the perspective of the table, you need to delete this entry from the corresponding bucket. If the corresponding conflict list is not empty, you need to modify the corresponding reference of the conflict list
- From the header’s point of view, you need to remove this entry from the bidirectional list and modify the corresponding references to the preceding and following elements in the list
-
Clear method parsing
public void clear() { super.clear();// All references to the header are redirected to themselves, equivalent to the position reset header.before = header.after = header;}
6. The LRU
- LRU algorithm: delete the data farthest from the current time when it was last used
- Since removeEldestEntry of LinkedHashMap is false by default, LRU cannot be implemented directly using LinkedHashMap.
- You can override removeEldestEntry by inheritting the LinkedHashMap
- RemoveEldestEntry method resolution
/ * ** By default, false is returned and elements are not deleted directly* /protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { return false; }
- Override the removeEldestEntry method
/ * ** If the value exceeds a constant, the delete function can be triggered.* Only core pseudocode implementations are provided here* /protected boolean removeEldestEntry(Map.Entry<K,V> eldest) { Return size() > the given maximum cache size;}