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 的值，返回 3
cache.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 的值，返回 1
System.out.println(cache.get(4)); // 获取键 4 的值，返回 7
}
}
时间复杂度：
get和put操作的时间复杂度均为O(1)。