package com.springboot.learn.redis;
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
private Map<Integer, Node> cache; // 哈希表用于快速查找节点
private int capacity; // LRU缓存的容量
private Node head; // 双向链表的头节点
private Node tail; // 双向链表的尾节点
public LRUCache(int capacity) {
this.cache = new HashMap<>(capacity); // 初始化哈希表
this.capacity = capacity; // 初始化容量
this.head = new Node(-1, -1); // 初始化头节点
this.tail = new Node(-1, -1); // 初始化尾节点
head.next = tail; // 头节点的下一个节点是尾节点
tail.prev = head; // 尾节点的上一个节点是头节点
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1; // 如果缓存中不存在该键，则返回 -1
}
Node node = cache.get(key); // 获取节点
moveToHead(node); // 将节点移到链表头部，表示最近访问过
return node.value; // 返回节点的值
}
public void put(int key, int value) {
if (cache.containsKey(key)) { // 如果缓存中已经存在该键
Node node = cache.get(key); // 获取节点
node.value = value; // 更新节点的值
moveToHead(node); // 将节点移到链表头部，表示最近访问过
} else { // 如果缓存中不存在该键
if (cache.size() == capacity) { // 如果缓存已满
Node lastNode = tail.prev; // 获取尾部节点，即最久未使用的节点
removeNode(lastNode); // 移除尾部节点
cache.remove(lastNode.key); // 从缓存中移除该节点的键
}
Node newNode = new Node(key, value); // 创建新节点
cache.put(key, newNode); // 将节点加入缓存
addNode(newNode); // 将节点添加到链表头部
}
}
private void moveToHead(Node node) {
removeNode(node); // 先将节点从链表中移除
addNode(node); // 再将节点添加到链表头部
}
private void addNode(Node node) {
node.next = head.next; // 新节点的下一个节点是头节点的下一个节点
head.next.prev = node; // 头节点的下一个节点的上一个节点是新节点
head.next = node; // 头节点的下一个节点是新节点
node.prev = head; // 新节点的上一个节点是头节点
}
private void removeNode(Node node) {
node.prev.next = node.next; // 被移除节点的上一个节点的下一个节点是被移除节点的下一个节点
node.next.prev = node.prev; // 被移除节点的下一个节点的上一个节点是被移除节点的上一个节点
}
private class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
}
