In this article, we began to analyze the source code of LinkedHashMap. LinkedHashMap inherits HashMap, which means that LinkedHashMap is extended based on HashMap. Therefore, before looking at the source code of LinkedHashMap, readers need to understand the source code of HashMap. You can check the introduction of my previous article "Java Collection Series [3]----HashMap Source Code Analysis". As long as you have a deep understanding of the implementation principle of HashMap, and then look at the source codes of LinkedHashMap, HashSet and LinkedHashSet are all very simple. Therefore, readers should be patient and study the HashMap source code. This is a good business of buying one get three free. When analyzing the HashMap source code earlier, I used problem-oriented analysis of the source code so that I would not analyze it randomly like a headless fly, and readers could also have a deeper understanding of the problem. In this article, I decided to use this method to analyze LinkedHashMap.
1. What kind of structure is used inside LinkedHashMap?
As you can see, since LinkedHashMap inherits from HashMap, there is still a hash table inside LinkedHashMap, but LinkedHashMap has rewritten an Entry and added two member variables to the original HashMap Entry, namely the previous node reference and the successor node reference. This way, all nodes are linked together to form a two-way linked list. When obtaining elements, just traverse the two-way linked list directly. Let's see what the LinkedHashMap implementation of Entry looks like.
private static class Entry<K,V> extends HashMap.Entry<K,V> { //Reference of the previous node of the current node in the bidirectional linked list Entry<K,V> before; //Reference of the subsequent node of the current node in the bidirectional linked list Entry<K,V> after; Entry(int hash, K key, V value, HashMap.Entry<K,V> next) { super(hash, key, value, next); } //Remove this node from the bidirectional linked list private void remove() { before.after = after; after.before = before; } //Insert the current node into an existing node in the bidirectional linked list private void addBefore(Entry<K,V> existentingEntry) { //The reference of the next node of the current node points to the given node after = existingEntry; //The reference of the previous node of the current node points to the previous node of the given node before = existingEntry.before; //The reference of the next node of the given node points to the current node before.after = this; //The reference of the previous node of the given node points to the current node after.before = this; } //Sorted in order of access, record each time the operation is obtained void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; //If sorted in access order if (lm.accessOrder) { lm.modCount++; //Remove yourself from the bidirectional linked list first; //Put yourself to the tail of the bidirectional linked list addBefore(lm.header); } } void recordRemoval(HashMap<K,V> m) { remove(); }}2. How does LinkedHashMap implement sorting in insertion order?
//The method that will be called in the put method of the parent class void addEntry(int hash, K key, V value, int bucketIndex) { //Calling the addEntry method of the parent class super.addEntry(hash, key, value, bucketIndex); //The following operation is convenient for LRU cache implementation. If the cache capacity is insufficient, remove the oldest element Entry<K,V> elderly = header.after; if (removeEldestEntry(eldest)) { removeEntryForKey(eldest.key); }}//The method void createEntry(int hash, K key, V value, int bucketIndex) { //First get the Entry HashMap of HashMap.Entry<K,V> old = table[bucketIndex]; //Wrap it into LinkedHashMap's own Entry<K,V> e = new Entry<>(hash, key, value, old); table[bucketIndex] = e; //Insert the current node to the tail of the bidirectional linked list e.addBefore(header); size++;}LinkedHashMap overrides the addEntry and createEntry methods of its parent class HashMap. When you want to insert a key-value pair, the put method of its parent class HashMap will be called first. In the put method, we will check whether the corresponding key exists in the hash table. If it exists, just replace its value directly. If it does not exist, call the addEntry method to create a new Entry. Note that at this time, LinkedHashMap's own addEntry method is called. We see the above code. In addition to calling back the addEldestEntry method of the parent class, this addEldestEntry will also call removeEldestEntry to remove the oldest element. This operation is mainly to implement the LRU algorithm, which will be discussed below. We see that LinkedHashMap also rewrites the createEntry method. When you want to create a new Entry, this method will be called. After each time the Entry is put into the hash table, the addBefore method will be called to insert the current node into the tail of the bidirectional linked list. In this way, the bidirectional linked list records the order of each node inserted. When obtaining elements, just traverse the bidirectional linked list. The following figure shows the operation of each call to addBefore. Since it is a bidirectional linked list, before inserting the current node into the head node, it is actually inserting the current node into the tail of the bidirectional linked list.
3. How to use LinkedHashMap to implement LRU cache?
We know that the implementation of cache depends on the computer's memory, and the memory resources are quite limited, and it is impossible to store elements without limit. Therefore, we need to appropriately delete some elements when the capacity is insufficient. So which element is better to delete? The idea of the LRU algorithm is that if a data has been accessed recently, the chances of being accessed in the future are also higher. So we can delete data that is not often accessed. Next, let’s take a look at how LinkedHashMap implements the LRU mechanism.
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> { //Bothly linked list header private transient Entry<K,V> header; //Sort private final boolean accessOrder in order of access; ... public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; } //Get value according to key public V get(Object key) { //Calling the parent class method to get the corresponding Entry Entry<K,V> e = (Entry<K,V>)getEntry(key); if (e == null) { return null; } //If it is sorted in access order, the node after each use will be placed at the end of the bidirectional linked list e.recordAccess(this); return e.value; } private static class Entry<K,V> extends HashMap.Entry<K,V> { ... //Insert the current node into front of an existing node in the bidirectional linked list private void addBefore(Entry<K,V> existingEntry) { //The reference of the next node of the current node points to the given node after = existingEntry; //The reference of the previous node of the current node points to the previous node of the given node before = existingEntry.before; //The reference of the next node of the given node points to the current node before.after = this; //The reference of the previous node of the given node points to the current node after.before = this; } //Sorted in access order, record each time the operation void recordAccess(HashMap<K,V> m) { LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m; //If sorted in access order if (lm.accessOrder) { lm.modCount++; //Remove yourself from the bidirectional linked list first; //Put yourself to the tail of the bidirectional linked list addBefore(lm.header); } } ... } //This method will be called in the parent class put method void addEntry(int hash, K key, V value, int bucketIndex) { //Calculate the parent class's addEntry method super.addEntry(hash, key, value, bucketIndex); //The following operation is convenient for LRU cache implementation. If the cache capacity is insufficient, remove the oldest element Entry<K,V> elderly = header.after; if (removeEldestEntry(eldest)) { removeEldestForKey(eldest.key); } } //Where to delete the oldest element? This method is designed to be overwritten by subclasses protected boolean removeEldestEntry(Map.Entry<K,V> elderly) { return false; }}To be more intuitive, I omitted some irrelevant code in the code posted above. We can see that LinkedHashMap has a member variable accessOrder, which records whether it needs to be sorted in order of access. It provides a constructor that can specify the value of accessOrder itself. Each time you call the get method to get the element, e.recordAccess(this) is called, which will move the current node to the end of the bidirectional linked list. Now we know that if accessOrder is true, then every time we get the element, we will move this element to the end of the bidirectional link list. The purpose of this step is to distinguish the most commonly used elements from those that are not often used, and the often used elements are placed at the end and the less commonly used elements are placed at the head. Let's go back to the above code and see that every time the addEntry method is called, we will determine whether the oldest element needs to be deleted. The logic of judgment is implemented by removeEldestEntry, which is designed to be overridden by subclasses and rewrite the logic inside. Note that since the recently visited nodes are moved to the tail of the bidirectional linked list, the oldest node is taken out from the head of the bidirectional linked list for deletion. The following example implements a simple LRU cache.
public class LRUMap<K, V> extends LinkedHashMap<K, V> { private int capacity; LRUMap(int capacity) { //Calling the parent class constructor, set to sort in access order super(capacity, 1f, true); this.capacity = capacity; } @Override public boolean removeEldestEntry(Map.Entry<K, V> elderly) { //When the key-value pair is greater than or equal to the hash table capacity return this.size() >= capacity; } public static void main(String[] args) { LRUMap<Integer, String> map = new LRUMap<Integer, String>(4); map.put(1, "a"); map.put(2, "b"); map.put(3, "c"); System.out.println("Original collection:" + map); String s = map.get(2); System.out.println("Get element:" + map); map.put(4, "d"); System.out.println("After insertion:" + map); } }The results are as follows:
Note: All the above analysis is based on JDK1.7, and there will be differences between different versions, readers need to pay attention.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.