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;}}