“This is my 28th day of participating in the First Challenge 2022. For details: First Challenge 2022.”

Redis LRU algorithm introduction

Title: 1, Redis LRU understand? Is it possible to write an LRU algorithm?

What is LRU?

LRU is the abbreviation of Least Recently Used, which is a commonly Used page replacement algorithm.

Select the most recent and longest unused data for elimination.

Source of algorithm Design

Force link (146 title LRU algorithm introduction) :

Leetcode-cn.com/problems/lr…

As shown in figure:

Design idea

1. The so-called cache must have read and write operations. According to the thought of hit ratio, the time complexity of write and read operations should be O(1).

2. Feature requirements

2.1 There must be a distinction between the ordering of recently used data and data that has not been used for a long time.

2.2 Write and read Operations Are performed at one time.

2.3 If the capacity (pit) is full to delete the least long use who, each new access to the new data in and out of the team head (according to the business of your own set which side is the team head).

Fast to find, fast to insert, fast to delete, and also sort —–> What kind of data structure can satisfy this problem?

Can you do both in O(1) time?

What data structure do you think works best if you can find it once?

The algorithm core of LRU is hash linked list

Essentially HashMap + DoubleLinkedList

Time complexity is a combination of O(1), hash and bidirectional linked lists.

LRU algorithm animation

LRU manual coding implementation

Implementation Case 1

Reference: LinkedHashMap

Relying on the JDK

public class Q149<K, V> extends LinkedHashMap<K, V> { private int capacity; // Cache pit public Q149(int capacity) {// true is the access order // false is the insert order super(capacity, 0.75f, true); this.capacity = capacity; } @Override protected boolean removeEldestEntry(Map.Entry<K, V> eldest) { return super.size() > capacity; } public static void main(String[] args) { Q149 q149 = new Q149(3); q149.put(1, "a"); q149.put(2, "b"); q149.put(3, "c"); System.out.println(q149.keySet()); q149.put(4, "d"); q149.put(5, "e"); System.out.println(q149.keySet()); }}Copy the code

Implementation Case 2

Do not rely on the JDK

Schematic data structure:

Create a Node object containing k, v attributes, and a pointer to the following object. 2. Construct a double-ended linked list DoubleLinkList to realize the cache data linked list structure. AddHead is used to update the first Node, and removeNode is used to remove the Node. And getLastNode to get the tail node. 3. Build an LRU structure by combining Map and DoubleLinkList. The whole is shown in the figure above

public class Q149_1 {

    // Map is responsible for finding and building a virtual bidirectional linked list, which is installed in a Node Node, as the carrier of data

    // 1 Constructs a Node as the data carrier
    class Node<K.V> {

        K key;
        V value;
        Node<K, V> prev;
        Node<K, V> next;

        public Node(a) {
            this.prev = this.next = null;
        }

        public Node(K key, V value) {
            this.key = key;
            this.value = value;

            this.prev = this.next = null; }}//2 Create a bidirectional queue containing our Node
    class DoubleLinkList<K.V> {
        Node<K, V> head;
        Node<K, V> tail;

        // 2.1 constructor
        public DoubleLinkList(a) {
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = this.tail;
            this.tail.prev = this.head;
        }

        // 2.2 Add a header
        public void addHead(Node<K, V> node) {
            node.next = head.next;
            node.prev = head;

            head.next.prev = node;
            head.next = node;
        }

        //2.3 Deleting a Node
        public void removeNode(Node<K, V> node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;

            node.prev = null;
            node.next = null;
        }

        //2.4 Get the last node
        public Node<K, V> getLast(a) {
            returntail.prev; }}private int cacheSize;

    private Map<Integer, Node<Integer, Integer>> map;

    private DoubleLinkList<Integer, Integer> doubleLinkList;

    public Q149_1(int cacheSize) {
        this.cacheSize = cacheSize;
        this.map = new HashMap<>();
        doubleLinkList = new DoubleLinkList<>();
    }

    public int get(int key) {
        if(! map.containsKey(key)) {return -1;
        }
        Node<Integer, Integer> node = map.get(key);
        doubleLinkList.removeNode(node);
        doubleLinkList.addHead(node);
        return node.value;
    }

    // save of update method
    public void put(int key, int value) {

        // update
        if (map.containsKey(key)) {
            Node<Integer, Integer> node = map.get(key);
            node.value = value;
            map.put(key, node);

            doubleLinkList.removeNode(node);
            doubleLinkList.addHead(node);
        } else {
            if (map.size() == cacheSize) {
                Node<Integer, Integer> lastNode = doubleLinkList.getLast();
                map.remove(lastNode.key);
                doubleLinkList.removeNode(lastNode);
            }

            / / new
            Node<Integer, Integer> newNode = newNode<>(key, value); map.put(key, newNode); doubleLinkList.addHead(newNode); }}public static void main(String[] args) {
        Q149_1 q149 = new Q149_1(3);
        q149.put(1.1);
        q149.put(2.2);
        q149.put(3.3);

        System.out.println(q149.map.keySet());

        q149.put(1.2);
        q149.put(2.1); System.out.println(q149.map.keySet()); }}Copy the code

The resources

• www.jianshu.com/p/12f025aba…