西安网站建设高端娄底建设网站

西安网站建设高端,娄底建设网站,做短视频必备的网站,成都市建设招标网站LRU#xff08;Least Recently Used#xff0c;最近最少使用#xff09;缓存淘汰策略的核心是#xff1a;当缓存容量满时#xff0c;淘汰最久未被使用的元素。在 Java 中#xff0c;最优实现方式是结合 HashMap#xff08;快速查找#xff09;和 LinkedList/LinkedHash…LRULeast Recently Used最近最少使用缓存淘汰策略的核心是当缓存容量满时淘汰最久未被使用的元素。在 Java 中最优实现方式是结合HashMap快速查找和LinkedList/LinkedHashMap维护访问顺序其中LinkedHashMap是官方推荐的简化实现方式而手动实现双链表 哈希表能更深入理解底层原理。一、核心原理数据结构选择哈希表HashMap存储「键 - 节点」映射实现 O (1) 时间复杂度的查找 / 更新。双向链表维护节点的访问顺序头部为最近使用的节点尾部为最久未使用的节点。核心操作get(key)若键存在将节点移到链表头部标记为最近使用返回值若不存在返回 -1。put(key, value)若键存在更新值并将节点移到链表头部若键不存在创建新节点并插入链表头部同时存入哈希表若缓存容量超限删除链表尾部节点最久未使用并从哈希表中移除对应键。二、手动实现链表 HashMap手动实现能清晰体现 LRU 的核心逻辑也是面试高频考点import java.util.HashMap; import java.util.LinkedList; import java.util.Map; public class LRUCacheK, V { private final int capacity; // 缓存容量 private final MapK, V cache; // 缓存键值对 private final LinkedListK keyList; // 维护key的访问顺序尾部最近使用头部最久未使用 // 初始化校验容量合法性 public LRUCache(int capacity) { if (capacity 0) { throw new IllegalArgumentException(缓存容量必须大于0); } this.capacity capacity; this.cache new HashMap(capacity); this.keyList new LinkedList(); } // put操作存入/更新key-value保证O(1)核心逻辑仅修复逻辑未优化性能 public synchronized void put(K key, V value) { // 1. 若key已存在先移除keyList中的旧位置再删除缓存旧值 if (cache.containsKey(key)) { keyList.remove(key); // 注意此处仍为O(n)后续优化会解决 cache.remove(key); } // 2. 若缓存已满删除最久未使用的key链表头部 if (cache.size() capacity) { K oldestKey keyList.removeFirst(); cache.remove(oldestKey); } // 3. 存入新值并将key加入链表尾部标记为最近使用 cache.put(key, value); keyList.addLast(key); } // get操作获取value并更新访问顺序 public synchronized V get(K key) { // 1. 缓存中不存在key返回null if (!cache.containsKey(key)) { return null; } // 2. 存在key更新访问顺序移除旧位置加入尾部 keyList.remove(key); // 此处仍为O(n)后续优化会解决 keyList.addLast(key); return cache.get(key); } // 辅助方法打印缓存和keyList用于测试 public void printCache() { System.out.println(缓存内容 cache); System.out.println(key访问顺序 keyList); } // 测试示例 public static void main(String[] args) { LRUCacheInteger, String lru new LRUCache(2); lru.put(1, A); lru.put(2, B); lru.printCache(); // 缓存{1A, 2B}keyList[1,2] lru.get(1); // 访问1更新顺序 lru.printCache(); // 缓存{1A, 2B}keyList[2,1] lru.put(3, C); // 容量满删除最久未使用的2 lru.printCache(); // 缓存{1A, 3C}keyList[1,3] lru.put(1, AA); // 更新1的值更新顺序 lru.printCache(); // 缓存{1AA, 3C}keyList[3,1] } }三、性能优化解决 LinkedList.remove (key) 的 O (n) 问题要让get/put操作真正达到 O (1) 时间复杂度需替换 LinkedList 为「双向链表 哈希表记录节点」即我之前提到的手动实现双链表方案。以下是优化后的最终版本import java.util.HashMap; import java.util.Map; public class LRUCacheK, V { // 双向链表节点存储key、value以及前驱/后继节点 private static class NodeK, V { K key; V value; NodeK, V prev; NodeK, V next; public Node(K key, V value) { this.key key; this.value value; } } private final int capacity; // 缓存容量 private final MapK, NodeK, V nodeMap; // key - 节点O(1)查找 private final NodeK, V head; // 虚拟头节点最近使用 private final NodeK, V tail; // 虚拟尾节点最久未使用 // 初始化虚拟头尾节点相连避免空指针 public LRUCache(int capacity) { if (capacity 0) { throw new IllegalArgumentException(缓存容量必须大于0); } this.capacity capacity; this.nodeMap new HashMap(capacity); this.head new Node(null, null); this.tail new Node(null, null); head.next tail; tail.prev head; } // put操作存入/更新key-valueO(1)时间复杂度 public synchronized void put(K key, V value) { NodeK, V node nodeMap.get(key); if (node ! null) { // 1. key已存在更新value并移到头部最近使用 node.value value; moveToHead(node); return; } // 2. key不存在创建新节点 NodeK, V newNode new Node(key, value); nodeMap.put(key, newNode); addToHead(newNode); // 3. 缓存已满删除尾节点最久未使用 if (nodeMap.size() capacity) { NodeK, V tailNode removeTail(); nodeMap.remove(tailNode.key); } } // get操作获取value并更新访问顺序O(1)时间复杂度 public synchronized V get(K key) { NodeK, V node nodeMap.get(key); if (node null) { return null; } // 移到头部标记为最近使用 moveToHead(node); return node.value; } // 双向链表辅助方法均为O(1)操作 // 将节点添加到虚拟头节点之后最近使用位置 private void addToHead(NodeK, V node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 移除指定节点 private void removeNode(NodeK, V node) { node.prev.next node.next; node.next.prev node.prev; } // 将节点移到头部先移除再添加 private void moveToHead(NodeK, V node) { removeNode(node); addToHead(node); } // 移除尾节点最久未使用 private NodeK, V removeTail() { NodeK, V tailNode tail.prev; removeNode(tailNode); return tailNode; } // 辅助方法打印缓存用于测试 public void printCache() { StringBuilder sb new StringBuilder(); NodeK, V cur head.next; while (cur ! tail) { sb.append(cur.key).append().append(cur.value).append(, ); cur cur.next; } System.out.println(缓存内容最近使用→最久未使用 sb); } // 测试示例 public static void main(String[] args) { LRUCacheInteger, String lru new LRUCache(2); lru.put(1, A); lru.put(2, B); lru.printCache(); // 1A, 2B lru.get(1); lru.printCache(); // 2B, 1A1移到最近使用 lru.put(3, C); lru.printCache(); // 1A, 3C删除最久未使用的2 lru.put(1, AA); lru.printCache(); // 3C, 1AA更新1并移到最近使用 } }