LRU（Least Recently Used）算法的核心思想是：最近使用的数据将被保留，最久未使用的数据将被淘汰。这种策略适用于内存有限、但又需要高频访问的数据场景，比如缓存系统、页面置换算法等。

mysql的缓冲池就是使用的LUR

InnoDB缓冲池通过双向链表和哈希表实现LRU机制：

• 双向链表按访问时间排序，最新访问的缓存页在头部，最久未使用的在尾部

• 哈希表用于快速定位链表节点

代码实现

import java.util.HashMap;public class LRUCache<K, V> {// 链表节点对象private class Node {K key;V value;// 定义上下节点, prev=上一个节点, next=下一个节点Node prev, next;public Node(K key, V value) {this.key = key;this.value = value;}}private final int capacity;private final HashMap<K, Node> cache;// 定义头部节点和尾部节点, 这两个节点都不存储数据, 只做头尾指向使用private Node head, tail;public LRUCache(int capacity) {this.capacity = capacity;this.cache = new HashMap<>((int) ((capacity / 0.75) + 1));this.head = new Node(null, null);this.tail = new Node(null, null);this.head.next = this.tail;this.tail.prev = this.head;}public V get(K key) {Node node = this.cache.get(key);if (node == null) {return null;}// 将当前节点移动到头部节点this.moveToHead(node);return node.value;}public void put(K key, V value) {Node node = this.cache.get(key);if (node == null) {Node newNode = new Node(key, value);// 添加到头部节点, 新节点一定要使用添加, 不能使用移动, 因为新节点的上下节点指向还未赋值this.addToHead(newNode);this.cache.put(key, newNode);if (this.cache.size() > capacity) {// 移除尾部节点Node tailNode = this.removeTail();this.cache.remove(tailNode.key);}} else {node.value = value;// 移动到头部节点this.moveToHead(node);}}// 移动当前节点到头部节点private void moveToHead(Node node) {// 先移除当前节点, 保证原来链表的上下完整性this.removeNode(node);// 将当前节点添加到头部节点this.addToHead(node);}// 添加头部节点private void addToHead(Node node) {// 假设原来的链表结构: head <-> A, null <-> B <-> null, 其中B是当前节点// 现在的链表结构: head <-> B <-> A// 第一步, 修改B的上一个指向和下一个指向// 第二步, 修改head的下一个指向, 修改A的上一个指向node.prev = this.head;node.next = this.head.next;this.head.next.prev = node;this.head.next = node;}// 移除当前节点private void removeNode(Node node) {// 将[当前节点]的[上一个节点]的[下一个节点]指向[当前节点]的[下一个节点]// 将[当前节点]的[下一个节点]的[上一个节点]指向[当前节点]的[上一个节点]// 假设原来的链表结构: A <-> B <-> C, 其中B是当前节点// 原来的链表结构: A <-> B <-> C// 现在的链表结构: A <-> C, 这里做了两步, 修改A的下一个指向, 修改C的上一个指向node.prev.next = node.next;node.next.prev = node.prev;}// 移除尾部节点private Node removeTail() {// 获取最后一个节点Node node = this.tail.prev;// 移除当前节点this.removeNode(node);return node;}}