目录

一，LRU算法

二，使用场景

三，LRU算法实现

---

一，LRU算法

LRU-least recently used-最近最少使用算法，是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据。LRU常用语缓存系统的淘汰策略。

二，使用场景

（1）操作系统里面用于页面置换算法,当分配的内存页不够的时候，可以选择将最近最少使用的页面剔除出去

（2）Redis中的数据淘汰策略: 假设MySQL里面有2000w数据，但redis中只能存20w的数据，如何保证redis中的数据都是热点数据?

Redis 提供 6 种数据淘汰策略：

1. volatile-lru（least recently used）：从已设置过期时间的数据集（server.db[i].expires）中挑选最近最少使用的数据淘汰

2. volatile-ttl：从已设置过期时间的数据集（server.db[i].expires）中挑选将要过期的数据淘汰

3. volatile-random：从已设置过期时间的数据集（server.db[i].expires）中任意选择数据淘汰

4. allkeys-lru（least recently used）：当内存不足以容纳新写入数据时，在键空间中，移除最近最少使用的 key（这个是最常用的）

5. allkeys-random：从数据集（server.db[i].dict）中任意选择数据淘汰

6. no-eviction：禁止驱逐数据，也就是说当内存不足以容纳新写入数据时，新写入操作会报错。这个应该没人使用吧！

三，LRU算法实现

本质是通过哈希表辅以双向链表来实现，使用一个哈希表和一个双向链表维护所有在缓存中的键值对。

• 靠近尾部的键值对是最近使用过的，而靠近头部的是最久未使用的。
• 哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置。
• 

package com.example.lrucache;

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

/**
 * @Author YuLing
 * @Date 2024-04-07 8:36
 * @Description:
 * @Version 1.0
 */
public class LRUCache {//最近最少使用

    Node head;
    Node tail;
    int capacity;
    Map<Integer, Node> mp;

    public LRUCache(int capacity){
        this.capacity = capacity;
        mp = new HashMap<>();
        head = tail = null;
    }
    /**
     * 添加节点
     *
     * @param node
     */
    public void addNode(Node node) {//尾插法
        if (head == null) {//如果链表是空
            head = tail = node;
            return;
        }
        tail.next = node;
        node.prev = tail;
        node.next = null;
        tail = node;
    }

    /**
     * 移除结点
     * @param node
     */
    public void removeNode(Node node) {
        if (head == null && tail == null) {
            return;
        }
        if (node == head) {//删除头结点
            head = head.next;
            return;
        }
        if (node == tail) {//删除尾结点
            tail = tail.prev;
            return;
        }
        node.prev.next = node.next;//中间结点
        node.next.prev = node.prev;
    }


    public void put(int key, int value) {
        //如果已经存在
        if (mp.containsKey(key)) {//更新并且从链表中删除
            Node node = mp.get(key);
            node.value = value;
            removeNode(node);
            addNode(node);
        } else {
            //如果链表中不存在
            if (mp.size() >= this.capacity) {//删除头结点，然后插入
                int oldKey = head.key;
                removeNode(head);
                mp.remove(oldKey);//移除旧的
                Node node = new Node(key, value);
                addNode(node);
                mp.put(key, node);
            } else {
                Node node = new Node(key, value);//直接插入
                addNode(node);//添加新的
                mp.put(key,node);
            }
        }
    }

    public int get(int key) {
        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            removeNode(node);
            addNode(node);
            return node.value;
        }
        return -1;//不存在这个元素
    }

    static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node() {}

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        System.out.println(lruCache.get(1));
        lruCache.put(3,3);
        System.out.println(lruCache.get(2));
        lruCache.put(4,4);
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}