🔥 Shrimps will teach you how to implement LRU cache elimination strategy with linked lists.

This article has participated in the third “topic writing” track of the Denver Creators Training Camp. For details, check out: Digg Project | Creators Training Camp third is ongoing, “write” to make a personal impact.

Code shrimp is a sand carving and funny boy who likes listening to music, playing games and writing as well as most of his friends. The days are still very long, let’s refuel our efforts together 🌈

Welcome to follow my public account: JavaCodes, the name is with Java but the scope can be more than Java field oh 😁, will share blog posts or welfare for a long time, looking forward to your attention ❤

😉 offer yourself

Self-introduction, to everyone recommend their column 😁, welcome small partners to collect attention 😊

The small white to learn Java

MybatisPlus column

App crawler Column

PC side crawler column

Big factory interview question column

✨ LRU is introduced

According to Baidu Baike:LRU_ Baidu.com

LRU is the abbreviation of Least Recently UsedPage replacement algorithm, select the most recent unused page to be eliminated. The algorithm assigns eachpageAn access field is used to record the time t experienced by a page since it was visited last time. When it is necessary to eliminate a page, select the page with the largest T value in the existing page, that is, the least recently used page to be eliminated.

So what I would say is: eliminate the least recently used data

☀LRU usage scenario

LRU page replacement algorithm for operating system
The LRU algorithm used by the Mysql buffer pool manages data pages
Redis also has a cache elimination strategyVolatile - lru and allkeys - lruThese are the LRU algorithms used

🔥 implements the LRU algorithm

🔥 implement LRU – LRU related exercises

LRU algorithm link on the force link

It can be seen that the number of likes, comments and solutions of this question are very high

Cattle on the subject link

🔥 Implementing LRU – A summary of the premises ✨

How to use linked lists to implement LRU cache elimination strategy?

So the list used to implement LRU is not a normal list but a bidirectional list

And you won’t be asked to implement the LRU algorithm using existing libraries such as LinkedList, a collection class that uses linked lists at the bottom

So for bidirectional lists we need to do it manually

class DoubleLinkedList {
    int key;
    int value;
    DoubleLinkedList prev;
    DoubleLinkedList next;

    public DoubleLinkedList(a) {}public DoubleLinkedList(int key, int value) {
        this.key = key;
        this.value = value; }}Copy the code

In addition, we also define virtual head nodes and tail nodes to define the interval

🔥 Also, the number of use from the beginning node to the end node gradually decreases, that is, from the most recently used gradually to the least recently used!!

private DoubleLinkedList head,tail;
Copy the code

Having a bidirectional list is not enough, because LRU is the least recent use, so you also need to record the least use

So, we use a HashMap to keep track of the number of uses

private Map<Integer,DoubleLinkedList> map;
Copy the code

☀ That’s about it, then let’s move on to the complete code flow section

🔥 Implement LRU – full code annotation explanation ✨

import java.util.HashMap;
import java.util.Map;


public class LruDemo {

    // Define a bidirectional list
    class DoubleLinkedList {
        int key;
        int value;
        DoubleLinkedList prev;
        DoubleLinkedList next;

        public DoubleLinkedList(a) {}public DoubleLinkedList(int key, int value) {
            this.key = key;
            this.value = value; }}// Current capacity
    private int size;
    // Maximum capacity
    private int capacity;
    // Record the number of uses
    private Map<Integer,DoubleLinkedList> map;
    // Virtual head node and tail node
    private DoubleLinkedList head,tail;

    // The constructor is initialized
    public LruDemo(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap<>();
         // Use pseudo head and pseudo tail nodes
        this.head = new DoubleLinkedList();
        this.tail = new DoubleLinkedList();

        head.next = tail;
        tail.prev = head;
    }


    / / LRU - the get method
    public int get(int key) {
        // If there is no key
        if(! map.containsKey(key)) {return -1;
        }

        DoubleLinkedList node = map.get(key);
        
        // If the key is present, the hash table is used to locate the key, and then the hash table is used to locate the key.
        moveToHead(node);
        return node.value;
    }


    / / LRU - put method
    public void put(int key,int value) {

        DoubleLinkedList node = map.get(key);
	// If it does not exist
        if (node == null) {

            DoubleLinkedList newNode = new DoubleLinkedList(key, value);
            // Move the head node
            addHead(newNode);
            map.put(key,newNode);
            size++;
		   
            // If the capacity is full
            if (size > capacity) {
                // Delete the last node is the longest unusedDoubleLinkedList lastNode = removeLastNode(); map.remove(lastNode.key); size--; }}else {
            // Update the valuenode.value = value; moveToHead(node); }}// Delete the last node
    private DoubleLinkedList removeLastNode(a) {
        DoubleLinkedList last = tail.prev;

        removeNode(last);
        return last;
    }

    // Move the node to the head node
    private void moveToHead(DoubleLinkedList node) {
        removeNode(node);
        addHead(node);
    }

    // Delete a node
    private void removeNode(DoubleLinkedList node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
        node.next = null;
        node.prev = null;
    }

    // Add a node (default is to add the first node)
    private void addHead(DoubleLinkedList node) { node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; }}Copy the code

❤ finally

I am aCode pipi shrimp, a prawns lover who loves to share knowledge, will update useful blog posts in the future, looking forward to your attention!!

Creation is not easy, if this blog is helpful to you, I hope you can key three even oh! Thank you for your support, we will see you next time ~~~, no, we see 😊 every day