LinkedHashMap source code analysis

1. Basic structure

1. Realization

The implemented interface is map

2. Succession

   inheriting HashMap is familiar. In fact, we will see that the amount of code of LinkedHashMap is very small, mainly because the HashMap he inherits inherits inherits most operations. If you are more careful, you will find that there are many blank methods in HashMap. These methods are actually template methods. In order to let the classes that inherit HashMap rewrite some of their own features. Without breaking the code structure.

3. Data field

1. Basic fields

   on the basis of HashMap, he added three fields, which are very important. The first is about the two fields of the two-way linked list and the flag bit to decide whether to carry out LRU.

2. Entry node

  it may be clear from the previous analysis of HashMap source code that there is a treenode node, which inherits the entry node in LinkedHashMap. In this node, before and after are added to the node node of HashMap, that is, the pointer used to construct a two-way linked list.

4. Overview of key methods

2. Analysis of important methods

1. Construction method

   this class has five construction methods. At first, I thought there were only four like HashMap. Later, I found a deep hidden method, which is also the most important method to implement LRU.

    let's focus on the last special method. We have seen the previous methods, which are similar to those in HashMap, that is, there is an operation to set accessorder = false. In the last method, if we set accessorder = true, when we access an element, the element will automatically be arranged to the end of the two-way linked list. That is, the so-called LRU.

  since we mentioned the construction method, let's talk about the reinitialize method, which sets the head node and tail node. These methods are used in clone and deserialization.

2. afterNodeRemoval

This method is relatively simple. It is also a template method. Its main function is to modify the two-way linked list, so as to delete a node.

3. afterNodeInsertion

   after inserting the node, if the LRU algorithm we implemented needs to delete some old nodes, this method will automatically delete the old nodes after inserting the node. The deletion logic is determined by the removeeldestentry method. If you want to enable deletion, the deletion logic is made in this method and returns true. There is no implementation here!

4. afterNodeAccess

    it doesn't matter if we don't start the LRU algorithm after the node is accessed. The order remains unchanged after the access. If accessorder = true, the accessed elements must be placed at the end of the two-way linked list.

5. containsValue

Overriding the method of the parent class is mainly because the traversal will be faster with the support of two-way linked list.

6. get

Is the get method an access element or an LRU problem

7. removeEldestEntry

Empty implementation.

3. Summary

In fact, when we understand this container, we just treat it as a HashMap and add an irrelevant two-way pointer. Then pay attention to the use of his LRU algorithm!