Shulou(Shulou.com)06/02 Report--

This article focuses on "how to handwrite the simplest LRU algorithm", interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Now let the editor take you to learn "how to handwrite the simplest LRU algorithm"!

1 what is LRU

LRU (Least recently used) is the least used recently, and its core idea is that "if data has been accessed recently, it is more likely to be accessed in the future." Therefore, the LRU algorithm sorts the data according to its historical access history, and if there is not enough space, it will eliminate the least recently used data.

2 implementation principle of LRU

Because the LRU algorithm prioritizes the recently used data, the data structure is required to support sorting, and the linked list is very appropriate.

Why not consider arrays?

Because the LRU algorithm is generally used in frequently accessed scenarios, the data will be moved frequently, and once the array is moved, the location of all the data after moving to the value position needs to be changed, which is inefficient and is not recommended.

3 LinkedHashMap of two-way linked list

Earlier we analyzed the algorithm implementation of LRU, which can be implemented using linked lists. LinkedHashMap in java is a two-way linked list.

LinkedHashMap is a subclass of HashMap and maintains a two-way linked list that links all entry on top of the HashMap data structure, which defines the order of iterations, usually the order of data insertion.

Let's look at the source code of LinkedHashMap:

As you can see from the definition in the source code, the accessOrder attribute can specify the order in which the LinkedHashMap is traversed. True indicates that it is in the order of access, and false means that it is in the order of insertion. The default is false.

Because LRU is sensitive to access order, use true to simply verify:

Public class LRUTest {public static void main (String [] args) {LinkedHashMap map = new LinkedHashMap (16,0.75f, true); map.put ("a", 1); map.put ("b", 2); map.put ("c", 3); System.out.println ("before get" + map); map.get ("a"); System.out.println ("after get" + map) }}

The running results are as follows:

Before get {baked 1, baked 2, cased 3} after get {baked 2, cased 3, axed 1}

You can see that with accessOrder = true, you can have LinkedHashMap sort by access order.

So how does LinkedHashMap do it?

Let's take a look at the get method

Public V get (Object key) {Node e; / / get node if ((e = getNode (hash (key), key)) = = null) return null; / / if accessOrder = true, execute the afterNodeAccess method if (accessOrder) afterNodeAccess (e); return e.value;}

Let's take a look at the afterNodeAccess method, and we find that the principle of moving the node to this mobile node is understood.

Void afterNodeAccess (Node e) {/ / move node to last LinkedHashMap.Entry last; if (accessOrder & & (last = tail)! = e) {LinkedHashMap.Entry p = (LinkedHashMap.Entry) e, b = p.before, a = P.P.; 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;}}

At present, if we use LinkedHashMap for LRU, there is another problem that bothers us, that is, if the capacity is limited, how to eliminate the old data?

Let's look back at the put method.

Public V put (K key, V value) {return putVal (hash (key), key, value, false, true);} final V putVal (int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node [] tab; Node p; int n, I; if ((tab = table) = = null | (n = tab.length) = = 0) n = (tab = resize (). If ((p = tab [I = (n-1) & hash]) = = null) tab [I] = newNode (hash, key, value, null); else {Node e; K k; if (p.hash = = hash & & (k = p.key) = = key | | (key! = null & & key.equals (k) e = p Else if (p instanceof TreeNode) e = ((TreeNode) p) .putTreeVal (this, tab, hash, key, value); else {for (int binCount = 0;; + + binCount) {if ((e = p.next) = = null) {p.next = newNode (hash, key, value, null) If (binCount > = TREEIFY_THRESHOLD-1) / /-1 for 1st treeifyBin (tab, hash); break } if (e.hash = = hash & & (k = e.key) = = key | | (key! = null & & key.equals (k) break; p = e }} if (e! = null) {/ / existing mapping for key V oldValue = e.value; if (! onlyIfAbsent | | oldValue = = null) e.value = value; afterNodeAccess (e); return oldValue;}} + modCount; if (+ + size > threshold) resize () AfterNodeInsertion (evict); return null;} void afterNodeInsertion (boolean evict) {/ / possibly remove eldest LinkedHashMap.Entry first; if (evict & & (first = head)! = null & & removeEldestEntry (first)) {K key = first.key; removeNode (hash (key), key, null, false, true);}}

Looking at the put method step by step, we eventually find that if the removeEldestEntry (first) method returns true, the head is removed, thus eliminating data that has not been used recently. Fully compliant with LRU.

4 the simplest LRU implementation

According to the above analysis, we can implement the simplest LRU as follows

Public class LRUCache extends LinkedHashMap {private int cacheSize; public LRUCache (int cacheSize) {/ / Note: here you need to let accessOrder = true super (cacheSize, 0.75f, true); this.cacheSize = cacheSize;} / * to determine whether the number of elements exceeds the cache capacity, and remove * / @ Override protected boolean removeEldestEntry (Map.Entry eldest) {return size () > cacheSize }} at this point, I believe you have a deeper understanding of "how to handwrite the simplest LRU algorithm". You might as well do it in practice! Here is the website, more related content can enter the relevant channels to inquire, follow us, continue to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.