本文详细介绍如何使用 JavaScript 双向链表实现满足 O(1) 时间复杂度的 LRU 缓存算法。通过 Map 存储节点引用，利用双向链表维护访问顺序，实现 get 和 put 操作的高效执行。文章涵盖算法原理、硬件支持机制及完整代码实现。
目标
设计并实现一个符合 LRU（最近最少使用）缓存约束的数据结构。具体实现 LRUCache 类：LRUCache(int capacity) 使用正整数 capacity 初始化缓存容量；int get(int key) 若关键字 key 存在于缓存中，返回其值，否则返回 -1；void put(int key, int value) 若 key 已存在，更新其值；若不存在，插入该 key-value 对。当插入导致数量超过 capacity 时，需逐出最久未使用的关键字。get 和 put 操作均须保持 O(1) 的平均时间复杂度。
什么是 LRU
LRU 是 Least Recently Used 的缩写，意为最近最少使用，这是一种常见的页面置换算法，用于选择最近最久未使用的页面进行淘汰。该算法为每个页面分配一个访问字段，记录自上次访问以来经过的时间 t。当需要淘汰页面时，选择现有页面中 t 值最大者，即最近最少使用的页面进行淘汰。
简介
最近最少使用算法（LRU）是操作系统中为最大化页面命中率而广泛采用的置换算法。其核心思路是：发生缺页中断时，置换未使用时间最长的页面。从程序运行原理看，LRU 算法接近理想置换状态，既利用了内存中页面调用的历史信息，又准确反映了程序的局部性原理。利用 LRU 算法进行页面置换的结果如图 1 所示。当进程首次访问页面 2 时，由于页面 7 是最近最久未访问的，故将其置换。当首次访问页面 3 时，第 1 页成为最近最久未使用的页，被换出。由图 1 可见，前 5 个时间片的图像与最佳置换算法相同，但这并非必然。因为最佳置换算法基于“向后看”，依据后续页面使用情况；而 LRU 算法基于“向前看”，依据历史使用情况，页面过去与未来的走向之间并无必然联系。
硬件支持
尽管 LRU 置换算法性能优良，但需要较多的硬件支持。为了了解进程中各页面在内存中未被访问的时间，以及如何快速定位最近最久未使用的页面，系统需具备两类硬件之一：寄存器或栈。
寄存器
为记录进程中各页面的使用情况，需为内存中的每个页面配置一个移位寄存器，表示为
R = Rn-1 Rn-2 Rn-3 … R2 R1 R0
图 2 展示了某进程具有 8 个页面时的 LRU 访问情况。
当进程访问某物理块时，将相应寄存器的 Rn-1 位置为 1。此时，定时信号每隔一定时间（如 100 ms）将寄存器右移一位。若将 n 位寄存器的数值视为一个整数，则具有最小数值的寄存器对应的页面即为最近最久未使用的页面。图 2 展示了某进程在内存中具有 8 个页面，为每个内存页面配置一个 8 位寄存器时的 LRU 访问情况。这里，8 个内存页面的序号分别定为 1～8。由图可知，第 3 个内存页面的 R 值最小，发生缺页时，首先将其置换出去。
栈
图 3 展示了用栈保存当前使用页面时栈的变化情况。
可利用一个特殊栈保存当前使用的各个页面号。每当进程访问某页面时，将该页面号从栈中移出并压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程所访问的页面号序列为：
4，7，0，7，1，0，1，2，1，2，6
随着进程的访问，栈中页面号的变化情况如图 3 所示。在访问页面 6 时发生缺页，此时页面 4 是最近最久未被访问的页，应将其置换出去。
代码实现
思路
Map 使用一个 Map 来保存当前所有节点的信息，键为 key，值为链表中的具体节点。
链表
使用一个双向链表来记录当前节点的顺序。
链表节点数据结构
保存插入节点信息，pre 指向上一个节点，next 指向下一个节点。
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};链表数据结构
保存头结点 head 和尾结点 tail。
const linkLine = function () {
let head = new linkLineNode("head", "head");
let tail = new linkLineNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};链表头添加
将节点插入到头结点后面，修改头结点的 next 指向以及原本头结点的 next 节点的 pre 指向。
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};链表删除指点节点
重新指向节点前后节点的 next 和 pre 指向。
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};删除并返回链表的最后一个节点（非 tail）
取到链表的最后一个节点（非 tail 节点），删除该节点并返回节点信息。
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};打印链表信息
将链表的信息按顺序打印出来，入参为需要打印的属性。
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if (res != "") res += "-->";
res += h[key];
h = h.next;
}
console.log(res);
};LRUCache 数据结构
capacity 保存最大容量，kvMap 保存节点信息，linkLine 为节点的顺序链表。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkLine = new linkLine();
};get
如果关键字 key 存在于缓存中，则返回关键字的值，并重置节点链表顺序，将该节点移到头结点之后，否则返回 -1。
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};put
如果关键字 key 已经存在，则变更其数据值 value，并重置节点链表顺序，将该节点移到头结点之后；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node);
}
};完整代码
const linkLineNode = function (key = "", val = "") {
this.val = val;
this.key = key;
this.pre = null;
this.next = null;
};
const linkLine = function () {
let head = new linkLineNode("head", "head");
let tail = new linkLineNode("tail", "tail");
head.next = tail;
tail.pre = head;
this.head = head;
this.tail = tail;
};
linkLine.prototype.append = function (node) {
node.next = this.head.next;
node.pre = this.head;
this.head.next.pre = node;
this.head.next = node;
};
linkLine.prototype.delete = function (node) {
node.pre.next = node.next;
node.next.pre = node.pre;
};
linkLine.prototype.pop = function () {
let node = this.tail.pre;
node.pre.next = this.tail;
this.tail.pre = node.pre;
return node;
};
linkLine.prototype.myConsole = function (key = 'val') {
let h = this.head;
let res = "";
while (h) {
if (res != "") res += "-->";
res += h[key];
h = h.next;
}
console.log(res);
};
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.kvMap = new Map();
this.linkLine = new linkLine();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
this.linkLine.delete(node);
this.linkLine.append(node);
return node.val;
}
return -1;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
if (this.kvMap.has(key)) {
let node = this.kvMap.get(key);
node.val = value;
this.linkLine.delete(node);
this.linkLine.append(node);
} else {
let node = new linkLineNode(key, value);
if (this.capacity == this.kvMap.size) {
let nodeP = this.linkLine.pop();
this.kvMap.delete(nodeP.key);
}
this.kvMap.set(key, node);
this.linkLine.append(node);
}
};测试
var obj = new LRUCache(2);
obj.put(1, 1);
obj.put(2, 2);
console.log(obj.get(1)); //---> 1
obj.put(3, 3);
console.log(obj.get(2));//---> -1
obj.put(4, 4);
console.log(obj.get(1));//---> -1
console.log(obj.get(3));//---> 3
console.log(obj.get(4));//---> 4到此这篇关于 JavaScript 双向链表实现 LRU 缓存算法的示例代码的文章就介绍到这了，更多相关 JavaScript LRU 缓存算法内容请搜索本站以前的文章或继续浏览下面的相关文章希望大家以后多多支持本站！