LRU缓存（手写双向链表和哈希表）
就是采用淘汰策略，对于不咋进行调用得cache放到最后面
🌟 LRU 缓存实现详解（Java版）—— 哈希表 + 双向链表
LRU（Least Recently Used，最近最少使用）是一种经典的缓存淘汰策略。当缓存容量达到上限时，优先淘汰最久未被访问的数据。
本实现采用哈希表（HashMap） + 双向循环链表的方式，确保get和put操作的时间复杂度均为O(1)。
✅ 核心设计思路
- 哈希表（HashMap）：用于快速查找键值对，时间复杂度 O(1)。
- 双向循环链表：维护数据的访问顺序，最近使用的数据放在链表头部，最久未使用的在尾部。
- 虚拟头节点（dumNode）：简化链表操作，避免空指针判断。
- 访问即更新：每次
get或put已存在的键时，都将对应节点移到链表头部。 - 容量控制：当缓存超出容量时，删除链表尾部节点（最久未使用）。
class LRUCache { private static class Node{ int key,value; Node pre,next; Node(int k,int v){ this.key=k; this.value=v; } } private final HashMap<Integer,Node>hm=new HashMap<>(); private final int capacity; private final Node dumNode=new Node(0,0); public LRUCache(int capacity) { this.capacity=capacity; dumNode.pre=dumNode; dumNode.next=dumNode; } public int get(int key) { Node node=getNode(key); return node!=null?node.value:-1; } public void put(int key, int value) { Node node=getNode(key); if(node!=null){ node.value=value; return ; } node=new Node(key,value); hm.put(key,node); pushFront(node); if(hm.size()>capacity){ Node backNode=dumNode.pre; hm.remove(backNode.key); remove(backNode); } } private Node getNode(int key){ if(!hm.containsKey(key)){ return null; } Node node =hm.get(key); remove(node); pushFront(node); return node; } private void remove(Node node){ node.pre.next=node.next; node.next.pre=node.pre; } private void pushFront(Node node){ node.pre=dumNode; node.next=dumNode.next; dumNode.next=node; node.next.pre=node; } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */