Java算法之LRUCache缓存实现

实现一个LRU（最近最少使用）缓存可以通过使用HashMap和双向链表来实现。HashMap用于快速查找缓存中的元素，而双向链表用于维护元素的使用顺序

实现思路：

1.使用HashMap存储键值对，以便快速访问。
2.使用双向链表维护元素的使用顺序，最近使用的元素放在链表头部，最少使用的元素放在链表尾部。
3. 每次访问或插入元素时，将该元素移动到链表头部。
4.当缓存容量达到上限时，移除链表尾部的元素。
5. 定义一个内部类 Node，用于表示缓存中的每个元素。

package com.huawei.od.huawei.algorithm;import java.util.HashMap;/*** @ClassName: LRUCache缓存实现* @author: zengxianjin* @Desc: 实现一个LRU（最近最少使用）缓存可以通过使用HashMap和双向链表来实现。HashMap用于快速查找缓存中的元素，而双向链表用于维护元素的使用顺序* @create: 2024-09-03 16:39* @version: V1.0**/
public class LRUCache缓存实现 {//    使用HashMap存储键值对，以便快速访问。//    使用双向链表维护元素的使用顺序，最近使用的元素放在链表头部，最少使用的元素放在链表尾部。//    每次访问或插入元素时，将该元素移动到链表头部。//    当缓存容量达到上限时，移除链表尾部的元素。// 定义一个内部类 CacheNode，用于表示缓存中的每个元素。private class CacheNode {int key;   // 键int value; // 值CacheNode prev; // 指向前一个节点的引用CacheNode next; // 指向后一个节点的引用// Node 类的构造函数，初始化键和值。CacheNode(int key, int value) {this.key = key;this.value = value;}}// LRUCache 类的成员变量。private final int capacity; // 缓存的最大容量private final HashMap<Integer, CacheNode> map; // 用于存储键和对应节点的映射private final CacheNode head; // 双向链表的头部哨兵节点private final CacheNode tail; // 双向链表的尾部哨兵节点// LRUCache 类的构造函数，初始化缓存容量和映射，并设置哨兵节点。public LRUCache缓存实现(int capacity) {this.capacity = capacity;this.map = new HashMap<>();this.head = new CacheNode(0, 0); // 初始化头部哨兵节点this.tail = new CacheNode(0, 0); // 初始化尾部哨兵节点head.next = tail; // 头部哨兵节点指向尾部哨兵节点tail.prev = head; // 尾部哨兵节点指向头部哨兵节点}// get 方法，用于获取键对应的值。public int get(int key) {CacheNode node = map.get(key); // 从映射中获取节点if (node == null) {return -1; // 如果节点不存在，返回 -1}moveToHead(node); // 将节点移动到链表头部return node.value; // 返回节点的值}// put 方法，用于插入或更新键值对。public void put(int key, int value) {CacheNode node = map.get(key); // 从映射中获取节点if (node == null) {CacheNode newNode = new CacheNode(key, value); // 如果节点不存在，创建新节点map.put(key, newNode); // 将新节点添加到映射中addNode(newNode); // 将新节点添加到链表头部if (map.size() > capacity) { // 如果映射的大小超过容量，移除尾部节点CacheNode tail = popTail(); // 移除链表尾部节点map.remove(tail.key); // 从映射中移除对应的键}} else {node.value = value; // 如果节点存在，更新节点的值moveToHead(node); // 将节点移动到链表头部}}// addNode 方法，用于将节点添加到链表头部。private void addNode(CacheNode node) {node.prev = head; // 设置节点的前驱为头部哨兵节点node.next = head.next; // 设置节点的后继为头部哨兵节点的后继head.next.prev = node; // 将头部哨兵节点的后继的前驱设置为新节点head.next = node; // 将头部哨兵节点的后继设置为新节点}// removeNode 方法，用于从链表中移除节点。private void removeNode(CacheNode node) {CacheNode prev = node.prev; // 获取节点的前驱CacheNode next = node.next; // 获取节点的后继prev.next = next; // 将节点的前驱的后继设置为节点的后继next.prev = prev; // 将节点的后继的前驱设置为节点的前驱}// moveToHead 方法，用于将节点移动到链表头部。private void moveToHead(CacheNode node) {removeNode(node); // 首先从链表中移除节点addNode(node); // 然后将节点添加到链表头部}// popTail 方法，用于移除链表尾部的节点。private CacheNode popTail() {CacheNode res = tail.prev; // 获取尾部哨兵节点的前驱，即链表尾部的节点removeNode(res); // 从链表中移除节点return res; // 返回被移除的节点}// main 方法，用于演示 LRUCache 的使用。public static void main(String[] args) {LRUCache缓存实现 cache = new LRUCache缓存实现(2); // 创建一个容量为 2 的 LRU 缓存cache.put(1, 3); // 插入键值对 (1, 3)cache.put(2, 4); // 插入键值对 (2, 4)System.out.println(cache.get(1)); // 获取键 1 的值，返回 3cache.put(3, 1); // 插入键值对 (3, 1)，导致键 2 被淘汰System.out.println(cache.get(2)); // 获取键 2 的值，返回 -1（未找到）cache.put(4, 7); // 插入键值对 (4, 4)，导致键 1 被淘汰System.out.println(cache.get(1)); // 获取键 1 的值，返回 -1（未找到）System.out.println(cache.get(3)); // 获取键 3 的值，返回 1System.out.println(cache.get(4)); // 获取键 4 的值，返回 7}
}

时间复杂度：

get和put操作的时间复杂度均为O(1)。