LRU-least recently used-最近最少使用算法，是一种内存数据淘汰策略，使用常见是当内存不足时，需要淘汰最近最少使用的数据。LRU常用缓存的淘汰策略。
LRU的原理
这里的栈是一个特殊的栈，0 7调用时，会先入栈，到将1存放到内存时，会将7压出栈，当调用0时，栈底的0会先从栈中删除，再入栈， 新进入一个数据，会淘汰栈底的数据，访问栈中有的数据，该数据会先从栈中删除，再入栈。
基于HashMap+双向链表 实现LRU
HahsMap用于快速查找到结点的值，然后将使用到的结点放在对头，这样最近最少使用的结点自然就落入到队尾。双向链表提供了良好的灵活性，两边可达，更加方便实现特殊栈
实现的LRU操作双向链表部分的轨迹
save(key, value)：
首先在 HashMap 找到 Key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。
如果不存在，需要构造新的节点，并且尝试把节点塞到队头。
如果LRU空间不足，则通过 tail 淘汰掉队尾的节点，同时在 HashMap 中移除 Key。
get(key)：
通过 HashMap 找到 LRU 链表节点，因为根据LRU 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
实现代码：
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;// 实现一个基于最近最少使用（LRU）策略的缓存类
public class LRUCache {// 定义双向链表节点类class DLinkedNode {// 节点存储的键，类型为字符串String key;// 节点存储的值，类型为整数int value;// 指向前一个节点的引用DLinkedNode pre;// 指向后一个节点的引用DLinkedNode post;}// 使用 ConcurrentHashMap 来存储键和对应的双向链表节点，以实现快速查找private ConcurrentMap<String, DLinkedNode> cache = new ConcurrentHashMap<>();// 记录当前缓存中存储的元素数量private int count;// 缓存的最大容量，即最多能存储的元素数量private int capacity;// 双向链表的头节点，用于维护链表顺序private DLinkedNode head;// 双向链表的尾节点，用于维护链表顺序private DLinkedNode tail;// 构造函数，用于初始化缓存的容量public LRUCache(int capacity) {// 检查传入的容量是否为正整数，如果不是则抛出异常if (capacity <= 0) {throw new IllegalArgumentException("Capacity must be a positive integer.");}// 初始化当前元素数量为 0this.count = 0;// 设置缓存的最大容量this.capacity = capacity;// 创建头节点head = new DLinkedNode();// 头节点的前一个节点为空head.pre = null;// 创建尾节点tail = new DLinkedNode();// 尾节点的后一个节点为空tail.post = null;// 连接头节点和尾节点head.post = tail;tail.pre = head;}// 根据键从缓存中获取对应的值public int get(String key) {// 从缓存中查找对应的节点DLinkedNode node = cache.get(key);// 如果节点不存在，抛出异常提示键未找到if (node == null) {throw new IllegalArgumentException("Key not found in cache.");}// 将该节点移动到双向链表的头部，表示该节点最近被使用moveToHead(node);// 返回节点存储的值return node.value;}// 向缓存中插入或更新键值对public void put(String key, int value) {// 从缓存中查找对应的节点DLinkedNode node = cache.get(key);// 如果节点已存在if (node != null) {// 更新节点的值node.value = value;// 将该节点移动到双向链表的头部，表示该节点最近被使用moveToHead(node);// 操作完成，直接返回return;}// 创建一个新的节点DLinkedNode newNode = new DLinkedNode();// 设置新节点的键newNode.key = key;// 设置新节点的值newNode.value = value;// 将新节点放入缓存中cache.put(key, newNode);// 将新节点添加到双向链表的头部addNode(newNode);// 缓存中的元素数量加 1++count;// 如果缓存中的元素数量超过了最大容量if (count > capacity) {// 移除双向链表的尾节点（即最近最少使用的节点）DLinkedNode tail = popTail();// 从缓存中移除该尾节点对应的键值对cache.remove(tail.key);// 缓存中的元素数量减 1--count;}}// 将一个节点添加到双向链表的头部private void addNode(DLinkedNode node) {// 设置新节点的前一个节点为头节点node.pre = head;// 设置新节点的后一个节点为原来头节点的后一个节点node.post = head.post;// 更新原来头节点的后一个节点的前一个节点为新节点head.post.pre = node;// 更新头节点的后一个节点为新节点head.post = node;}// 从双向链表中移除一个节点private void removeNode(DLinkedNode node) {// 获取该节点的前一个节点DLinkedNode pre = node.pre;// 获取该节点的后一个节点DLinkedNode post = node.post;// 更新前一个节点的后一个节点为当前节点的后一个节点pre.post = post;// 更新后一个节点的前一个节点为当前节点的前一个节点post.pre = pre;}// 将一个节点移动到双向链表的头部private void moveToHead(DLinkedNode node) {// 先从链表中移除该节点removeNode(node);// 再将该节点添加到链表头部addNode(node);}// 移除并返回双向链表的尾节点private DLinkedNode popTail() {// 获取尾节点的前一个节点（即要移除的节点）DLinkedNode res = tail.pre;// 从链表中移除该节点removeNode(res);// 返回被移除的节点return res;}
}测试类
public class TestLRU {public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put("key1", 1);cache.put("key2", 2);System.out.println(cache.get("key1")); // returns 1cache.put("key3", 3); // evicts key2System.out.println(cache.get("key2")); // returns -1 (not found)cache.put("key4", 4); // evicts key1System.out.println(cache.get("key1")); // returns -1 (not found)System.out.println(cache.get("key3")); // returns 3System.out.println(cache.get("key4")); // returns 4}
}
获取key2的值
再次获取key 1
 aws cloudfront hands on)
