环境 Deno2.6.8 TypeScript
概述
LRU 缓存淘汰算法就是一种常用的策略，全称为 Least Recently Used，也就是我们认为最近使用过的数据应该是 “有用的”，很久没有用过的数据应该就是无用的，内存满了就应该先删除那些很久没用过的数据
常用于有限容量的缓存优化
LRU算法设计
cache 这个数据结构必备的条件如下：
显然 cache 中的元素必须有序，从而可以区分最近使用和久未使用的数据，当容量满了之后要删除最久未使用的那个元素来腾出位置。
要在 cache 中快速找到某个 key 是否存在并得到对应的 val
每次访问 cache 中的某个 key，需要将这个元素变为最近使用的，也就是说 cache 要支持在任意位置的快速插入和删除元素。
因此采用哈希链表数据结构实现该算法：
结合了哈希表查找快速和双向链表插入删除高效
如果每次默认从链表尾部添加元素，那么显然越靠近尾部的元素就是最近使用的，越靠近头部的元素就是越久未使用的。
对于某一个 key，可以通过哈希表快速定位到链表中的节点，从而取得对应的 val
链表显然是支持在任意位置快速插入和删除的，改改指针就可以了。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到任意一个链表节点，然后进行插入和删除
双向链表节点
/**
* LRU存储节点
*/
export class Node<K, V> {
/**
* LRU 存储节点构造函数
* @param key 节点键
* @param value 节点值
* @param prev
* @param next
*/
constructor(
public key?: K,
public value?: V,
public prev: Node<K, V> | null = null,
public next: Node<K, V> | null = null
) {}
}LRU Cache实现类
export class LRUCache<K, V> {
/**
* LRU容量
*/
private capacity: number = 0;
/**
* 哈希LRU节点哈希表
*/
private map: Map<K, Node<K, V>>;
/**
* 虚拟节点： next
*/
private head: Node<K, V>;
/**
* 虚拟尾节点： prev
*/
private tail: Node<K, V>;
constructor(capacity: number) {
if (!Number.isInteger(capacity) || capacity <= 0) {
throw new Error('缓存容量必须是一个正整数');
}
this.capacity = capacity;
this.map = new Map<K, Node<K, V>>();
// 初始化虚拟头尾节点
this.head = new Node<K, V>();
this.tail = new Node<K, V>();
// LRUCache为空时头尾虚拟节点合并
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 工具方法
/**
* 在末尾添加一个节点
* @param node
*/
private addToTail(node: Node<K, V>) {
node.prev = this.tail.prev; // 新节点指向末尾节点
this.tail.prev!.next = node; // 末尾节点指向新节点
this.tail.prev = node; // 虚拟节点指向到新节点
node.next = this.tail;
}
/**
* 删除某个节点
* @param node
*/
private removeNode(node: Node<K, V>) {
const prevNode = node.prev; // 前驱节点
const nextNode = node.next; // 后继节点
// 避开目标节点
prevNode!.next = nextNode;
nextNode!.prev = prevNode;
// 目标节点脱离链表
node.prev = null;
node.next = null;
}
/**
* 将节点移动到末尾
* @param node
*/
private moveToTail(node: Node<K, V>) {
this.removeNode(node);
this.addToTail(node);
}
/**
* 取出LRU缓存值，返回 -1表示不存在
* @param key
* @returns
*/
public get(key: K): V | undefined {
if (!this.map.has(key)) return undefined;
const node = this.map.get(key);
this.moveToTail(node!);
return node!.value as V;
}
public put(key: K, value: V) {
if (this.map.has(key)) {
// 从哈希表获取并更新节点
const node = this.map.get(key);
node!.value = value;
this.moveToTail(node!);
} else {
// 新增节点
if (this.capacity === this.map.size) {
const firstNode = this.head.next!;
// 先删除头节点(已过期)
this.removeNode(firstNode); // 链表
this.map.delete(firstNode.key!); // 哈希表
}
const newNode = new Node<K, V>(key, value);
this.addToTail(newNode);
this.map.set(key, newNode);
}
}
}测试
import { LRUCache } from './LRU.ts';
Deno.test('测试LRU算法', () => {
const cache = new LRUCache<number, number>(2); // 缓存容量为2
cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
console.log(cache.get(1)); // 返回 1
// cache = [(1, 1), (2, 2)]
// 因为最近访问了键 1，所以提至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入到队头
console.log(cache.get(2)); // 返回-1（未找到）
// cache = [(3, 3), (1, 1)]
// cache 中已经不存在键为 2 的数据
cache.put(1, 4);
// cache = [(1, 4), (3, 3)]
// 键1已经存在，更新对应的值，并将其提前到队头
console.log(cache.get(1)); // 返回 4
});
LRU缓存 + TTL
/**
* @param {number} capacity
*/
const LRUCache = function (capacity) {
this.head = new ListNode();
this.tail = new ListNode();
this.cap = capacity;
this.hashMap = new Map();
// 形成闭环，防止边界冗余操作
this.head.next = this.tail;
this.tail.pre = this.head;
};
/**
*
* @param {ListNode} node
*/
LRUCache.prototype.moveToEnd = function (node) {
this.removeNodeFromLinkList(node);
this.addToEnd(node);
};
/**
*
* @param {ListNode} node
*/
LRUCache.prototype.removeNodeFromLinkList = function (node) {
// 因为LRU缓存链表是闭环的，两个节点必然存在
const preNode = node.pre;
const nextNode = node.next;
// 引用绕过 node, 不做除了LinkList以外操作
preNode.next = nextNode;
nextNode.pre = preNode;
};
/**
*
* @param {ListNode} node
*/
LRUCache.prototype.addToEnd = function (node) {
// 尾节点指向 node
this.tail.pre.next = node;
node.pre = this.tail.pre;
// 更新尾虚拟节点指向
this.tail.pre = node;
node.next = this.tail;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const node = this.hashMap.get(key);
if (!node) {
return -1;
}
// 判断是否过期
if (node.expire <= Date.now()) {
this.removeNodeFromLinkList(node);
this.hashMap.delete(node.key);
return -1;
}
this.moveToEnd(node);
return node.val;
};
/**
* @param {number} key
* @param {number} value
* @param {number} TTL
* @return {void}
*/
LRUCache.prototype.put = function (key, value, TTL) {
const node = this.hashMap.get(key);
if (node) {
node.val = value;
// 更新时间戳
node.expire = Date.now() + TTL;
this.moveToEnd(node);
} else {
const curr = new ListNode(key, value, Date.now() + TTL);
// 缓存已满，先删除旧数据
if (this.cap === this.hashMap.size) {
// ❌：先把头节点从链表删除了，再删除哈希表中原头节点的下一个节点删除，导致映射依赖混乱
// this.removeNodeFromLinkList(this.head.next);
// this.hashMap.delete(this.head.next.key);
const oldNode = this.head.next;
this.removeNodeFromLinkList(oldNode);
this.hashMap.delete(oldNode.key);
}
this.addToEnd(curr);
this.hashMap.set(key, curr);
}
};
/**
* 遍历所有节点，删除过期节点
*/
LRUCache.prototype.clean = function () {
let curr = this.head.next;
while (curr !== this.tail) {
const next = curr.next; // 暂存，防止引用失效
if (curr.expire <= Date.now()) {
this.removeNodeFromLinkList(curr);
this.hashMap.delete(curr.key);
}
curr = next;
}
};
/**
* @param {number | undefined} key
* @param {number | undefined} val
* @param {ListNode | null} pre
* @param {ListNode | null} next
*/
function ListNode(key, val, expire, pre = null, next = null) {
this.key = key;
this.val = val;
this.pre = pre;
this.next = next;
this.expire = expire;
}
/**
* 注意事项：边界处理、虚拟节点、辅助函数解耦、权责分明
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/
原创
LRU 算法
本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
评论交流
欢迎留下你的想法