Redis中的LRU是真的LRU吗？

结论

redis的lru不是严格的lru，而是近似的lru

区别

1. 传统精度lru:需要维护有序链表，淘汰时找到全局最久未访问的key
2. redis lru:不会遍历所有key,采用随机采样策略，只在采样集合内删除闲置最久的key

为什么不实现真正的LRU

每次读写key,都需要把节点移动到链表头部
大量链表修改操作,单线程高并发场景绘产生性能损耗，内存上还需要额外存储链表指针

参考——LRU的java实现

package org.example;

import java.util.HashMap;

public class LRUCache {
    static class Node {
        String key;
        String val;
        Node prev, next;
        Node(String k, String v) {
            key = k;
            val = v;
        }
    }

    private final int capacity;
    private final HashMap<String, Node> map;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public String find(String key) {
        if (!map.containsKey(key)) return "";
        Node node = map.get(key);
        moveToTail(node);
        return node.val;
    }

    public boolean set(String key, String value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToTail(node);
            return true;
        }
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        addTail(newNode);

        if (map.size() > capacity) {
            Node del = removeHead();
            map.remove(del.key);
        }
        return false;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void addTail(Node node) {
        node.prev = tail.prev;
        node.next = tail;
        tail.prev.next = node;
        tail.prev = node;
    }

    private void moveToTail(Node node) {
        removeNode(node);
        addTail(node);
    }

    private Node removeHead() {
        Node first = head.next;
        removeNode(first);
        return first;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.set("1", "A");
        cache.set("2", "B");
        cache.set("3", "C");
        cache.find("1");
        cache.set("4", "D");

        System.out.println(cache.find("2")); // ""
        System.out.println(cache.find("1")); // A
    }
}