js实现 LRU 算法
2023-06-13 09:11:03 时间
方式一:map实现
class LRU {
constructor(size) {
this.size = size;
this.cache = new Map();
}
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
return -1;
}
put(key, val) {
if (this.cache.has(key)) {
this.cache.delete(key);
}
if (this.cache.size >= this.size) {
// 如果当前缓存的map 的长度超出限制,则删除最前面的一个映射keys.next().value 可以拿到第一个映射的 key
this.cache.delete(this.cache.keys().next().value);
}
this.cache.set(key, val);
}
}
const lruCache = new LRU(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
const res1 = lruCache.get(1);
lruCache.put(3, 3);
const res2 = lruCache.get(2);
lruCache.put(4, 4);
const res3 = lruCache.get(1);
const res4 = lruCache.get(3);
const res5 = lruCache.get(4);
console.log("LRU", res1, res2, res3, res4, res5); // 1 -1 -1 3 4
方式二:map+双向链表
class DoubleNode {
constructor(element) {
this.element = element;
this.next = null;
this.prev = null;
}
}
class LRUCache2 {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.cache = new Map();
this.head = new DoubleNode();
this.tail = new DoubleNode();
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.moveToHead(node);
return node.element.value;
}
put(key, value) {
if (!this.cache.has(key)) {
const node = new DoubleNode({
key,
value,
});
this.cache.set(key, node);
this.addToHead(node);
this.size++;
if (this.size > this.capacity) {
const removed = this.removeTail();
console.log("removed===", removed);
this.cache.delete(removed.element.key);
this.size--;
}
} else {
const node = this.cache.get(key);
node.element.value = value;
this.moveToHead(node);
}
}
addToHead(node) {
// 双向链表新增节点处理四种指向:当前节点的上一个和下一个节点指向,当前节点的上一个节点的下一个节点指向,当前节点的下一个节点的上一个节点指向
node.prev = this.head;
node.next = this.head.next;
this.head.next.prev = node;
this.head.next = node;
}
removeNode(node) {
// 双向链表删除节点处理两种指向:删除节点的上一个节点的下一个节点指向,删除节点的下一个节点的上一个节点指向
node.prev.next = node.next;
node.next.prev = node.prev;
}
moveToHead(node) {
this.removeNode(node);
this.addToHead(node);
}
removeTail() {
const node = this.tail.prev;
this.removeNode(node);
return node;
}
}
const lruCache2 = new LRUCache2(2);
lruCache2.put(1, 1);
lruCache2.put(2, 2);
const res11 = lruCache2.get(1);
// console.log("res11", res11);
lruCache2.put(3, 3);
const res22 = lruCache2.get(2);
// console.log("res22", res22);
lruCache2.put(4, 4);
const res33 = lruCache2.get(1);
const res44 = lruCache2.get(3);
const res55 = lruCache2.get(4);
console.log(res11, res22, res33, res44, res55); // 1 -1 -1 3 4
相关文章
- Fabric.js 使用纯色遮挡画布(前景色)
- JS算法探险之栈(Stack)
- labuladong的算法小抄之js实现-第0章-学习算法和刷题的框架思维
- js三目运算符多条表达式_递归算法js
- js定时器与延时器_JS做定时器倒计时
- Js生成二维码_js在线生成二维码
- 常见的js算法_javascript数据结构与算法
- 括号匹配算法的JS简单实现
- JS将常用值转换为字符串
- 创建JS文件:在Linux下实现自动化任务(linux创建js文件)
- 使用JS实现Redis数据读取(js读取redis)
- 利用 JS 实现 Redis 的连接(js连接redis)
- 使用JS技术实现Oracle数据库链接(js 链接 oracle)
- JavaScript探索之旅掌握Oracle和JS的完美融合(js与oracle)
- Redis中的订阅机制及其在JS中的应用(redis 订阅 js)
- 初学prototype,发个JS接受URL参数的代码
- js模仿网上的限时抢购效果
- JS维吉尼亚密码算法实现代码
- js延迟加载改变JS的位置加快网页加载速度
- js获取坐标通过JS得到当前焦点(鼠标)的坐标属性
- 很好用的js日历算法详细代码
- js模仿windows桌面图标排列算法具体实现(附图)
- JS的千分位算法实现思路
- intro.js页面引导简单用法分享
- js中符号转意问题示例探讨
- js动态修改input输入框的type属性(实现方法解析)
- js获取当前路径的简单示例代码
- js给页面加style无效果的解决方法
- 用js正确判断用户名cookie是否存在的方法
- js使用for循环查询数组中是否存在某个值