设计LRU缓存结构

1. 什么是LRU缓存？

LRU缓存是一种基于最近访问原则的缓存策略。它的核心思想是，当缓存空间满时，优先淘汰最近最少使用的数据。这种策略的好处是，可以保留最常访问的数据，提高缓存命中率，从而提高系统性能。

2. LRU缓存的实现原理

LRU缓存的实现可以借助哈希表和双向链表。哈希表用于快速查找缓存中的数据，而双向链表用于维护数据的访问顺序。每当访问一个数据时，如果数据已经存在于缓存中，将其移动到链表的头部；如果数据不存在于缓存中，将其添加到链表的头部。当缓存空间满时，淘汰链表尾部的数据即可。

3. LRU缓存的实现步骤

- 初始化缓存大小和哈希表

- 访问数据时，检查哈希表中是否存在该数据

- 如果存在，将数据移动到链表头部

- 如果不存在，将数据添加到链表头部，并在哈希表中添加对应的键值对

- 如果缓存已满，删除链表尾部的数据，并在哈希表中删除对应的键值对

4.具体实现

public class LRUCache {    //链表存储键值对(旧数据靠链表尾)    class Node {        int key;        int value;        Node prev;        Node next;        public Node(int key, int value) {            this.key = key;            this.value = value;        }    }    //缓存大小    private int capacity;    //缓存    private Map cache;    //头指针    private Node head;    //尾指针组成双向链表    private Node tail;    //初始化缓存    public LRUCache(int capacity) {        this.capacity = capacity;        this.cache = new HashMap<>();        this.head = new Node(0, 0);        this.tail = new Node(0, 0);        head.next = tail;        tail.next = head;    }    //获取缓存数据    public int get(int key) {        if (cache.containsKey(key)) {            Node node = cache.get(key);            //更新数据(把该数据放到链表头)            removeNode(node);            addToHead(node);            return node.value;        }        //不存在则返回-1        return -1;    }    //存放数据    public void put(int key, int value) {        //包含则更新，不然新增        if (cache.containsKey(key)) {            Node node = cache.get(key);            node.value = value;            //更新数据            removeNode(node);            addToHead(node);        } else {            //大于容量,则删除最后一个值(最不经常使用的数据)            if (cache.size() == capacity) {                Node tailPrev = tail.prev;                removeNode(tailPrev);                cache.remove(tailPrev.key);            }            Node newNode = new Node(key, value);            cache.put(key, newNode);            addToHead(newNode);        }    }    //删除链表节点    private void removeNode(Node node) {        Node prevNode = node.prev;        Node nextNode = node.next;        prevNode.next = nextNode;        nextNode.prev = prevNode;    }    //头部插入节点    private void addToHead(Node node) {        Node nextNode = head.next;        head.next = node;        node.prev = head;        node.next = nextNode;        nextNode.prev = node;    }}

来源地址：https://blog.csdn.net/DU9999999/article/details/133036160