当前位置：首页 > backend >正文

LRU Java实现

backend 2025/5/19 20:31:36

总结下来，步骤大致是：

定义节点类，包含前驱、后继、键和值。
定义LRUCache类，包含容量、哈希表、头尾哑节点。
初始化时，创建头尾节点并连接，方便插入和删除操作。
get方法：如果存在节点，移动它到头部，返回值；否则返回-1。
put方法：如果存在节点，更新值并移动；否则创建新节点，添加到哈希表和链表头部，检查容量，超限则删除尾部节点。
辅助方法：添加节点到头部，删除节点，移动节点到头部，删除尾部节点。
这样应该就能正确实现LRU缓存了。然后，复杂度分析则是每个操作都是O(1)，因为哈希表和双向链表的操作都是常数时间。
在这里插入图片描述

import java.util.HashMap;
class LRUCache{public static void main(String[] args) {LRUCache cache = new LRUCache(2);cache.put(1,11);cache.put(2,22);cache.put(3,33);cache.get(2);cache.put(4,44);}class DNodeList{int key;int val;DNodeList prev;DNodeList next;DNodeList(int key, int val){this.key = key;this.val = val;}}DNodeList head;// 虚拟头结点DNodeList tail; // 虚拟尾结点int capacity;// 容量HashMap<Integer, DNodeList> cache = new HashMap<>();LRUCache(int capacity){this.capacity = capacity;head = new DNodeList(-1, -1);tail = new DNodeList(-1, -1);head.next = tail;tail.prev = head;}// 存储节点的Hash表// 获取值int get(int key){if(!cache.containsKey(key)){return -1;}DNodeList node = cache.get(key);// 移动到头部moveToHead(node);return node.val;}// 放置值void put(int key, int val){if(cache.containsKey(key)){DNodeList node = cache.get(key);node.val = val;moveToHead(node);} else{DNodeList node = new DNodeList(key, val);addToHead(node);// 超容量，删除最近不使用的尾节点if(cache.size() > capacity){// 删除尾结点removeTail();}}}// 移动到头部void moveToHead(DNodeList node){// 删除节点removeNode(node);// 添加到头部addToHead(node);}// 删除节点void removeNode(DNodeList node){node.prev.next = node.next;node.next.prev = node.prev;cache.remove(node.key);}// 添加到头部void addToHead(DNodeList node){node.next = head.next;head.next.prev = node;head.next = node;node.prev = head;cache.put(node.key, node);}// 删除尾结点void removeTail(){removeNode(tail.prev);}}