使用 js 实现一个 lru cache
Issue 欢迎在 Gtihub Issue 中回答此问题: Issue 251 (opens in a new tab)
Author 回答者: mrrs878 (opens in a new tab)
可以借助Map
实现
class LRUCache {
constructor(limit) {
this.limit = limit;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) return undefined;
const value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
}
put(key, value) {
if (this.cache.has(key)) this.cache.delete(key);
else if (this.cache.size >= this.limit) {
this.cache.delete(this.cache.keys().next().value);
}
this.cache.set(key, value);
}
}
// ["LRUCache","put","put","get","put","get","put","get","get","get"]
// [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
const lruCache = new LRUCache(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(res1, res2, res3, res4, res5);
// 1 undefined undefined 3 4
Author 回答者: haotie1990 (opens in a new tab)
LRU (最近最少使用) 缓存机制
- 使用Map做数据保存
- 自建双向链表做元素使用频率保存及空间大小控制
Author 回答者: 4may-mcx (opens in a new tab)
数组存key + map
class LRUCache {
_stack = [];
_map = {};
constructor(len = 10) {
this._len = len;
}
put(key, value) {
if (this._stack.includes(key)) {
this.update(key, value);
return;
}
// 如果超过缓存的大小,那就删除数组中的最后一个值
if (this._stack.length >= this._len) {
const delKey = this._stack[this._len - 1];
this.delete(delKey);
}
this.set(key, value);
}
set(key, value) {
this._stack.unshift(key);
this._map[key] = value;
}
get(key) {
if (this._map[key]) {
this.update(key);
return this._map[key];
}
return -1;
}
update(key, value) {
const index = this._stack.indexOf(key);
this._stack.splice(index, 1);
this._stack.unshift(key);
if (value) {
this._map[key] = value;
}
}
delete(key) {
delete this._map[key];
this._stack.pop();
}
}
export default LRUCache;
Author 回答者: iamphc (opens in a new tab)
function Node(key, val) {
this.prev = null;
this.next = null;
this.key = key;
this.val = val;
}
function DoubleList() {
this._node = new Node(null, null);
this.size = 0;
// 插入到头部
this.addFirst = (node) => {
// 找到头节点
while (this._node) {
this._node = this._node.prev;
}
// 处理头节点
this._node.prev = node;
node.next = this._node;
// 找到尾节点
while (this._node) {
this._node = this._node.next;
}
// 处理尾节点
this._node.prev.next = null;
this._node.prev = null;
this.size++;
};
// 移除一个节点
this.remove = (node) => {
if (!this.size) return -1;
const prev = node.prev;
const next = node.next;
if (prev) {
node.prev.next = node.next;
}
if (next) {
node.next.prev = node.prev;
}
this.size--;
};
// 移除最后一个节点,并返回该节点
this.removeLast = () => {
if (!this.size) return -1;
while (this._node) {
this._node = this._node.next;
}
this.remove(this._node);
return this._node;
};
}
function LRUcache(limit) {
this._limit = limit;
this._doubleList = new DoubleList();
this._map = new Map();
// 获取key对应的节点,并将节点提前
this.get = (key) => {
if (!this._map.has(key)) return -1;
const node = this._map.get(key);
this._doubleList.addFirst(node);
return node;
};
// 插入节点,并将节点提前
this.put = (key, val) => {
const node = new Node(key, val);
if (this._map.has(key)) {
this._doubleList.remove(this._map.get(key));
}
if (this._doubleList.size === this._limit) {
const lastNode = this._doubleList.removeLast();
this._map.delete(lastNode.key);
}
this._doubleList.addFirst(node);
this._map.set(key, node);
};
}