# 如何实现一个 LRU
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 94 (opens new window)
Author
leetcode149
- 用双向链表+哈希。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.map = new Map();
this.cache = new DoubleList();
};
class Node {
constructor(k, val) {
this.k = k;
this.val = val;
this.pre = null;
this.next = null;
}
}
class DoubleList {
constructor() {
this.size = 0;
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.pre = this.head;
}
addLast(x) {
const { head, tail } = this;
x.pre = tail.pre;
x.next = tail;
tail.pre.next = x;
tail.pre = x;
this.size++;
}
remove(x) {
x.pre.next = x.next;
x.next.pre = x.pre;
this.size--;
}
removeFirst() {
const { head, tail } = this;
if (head.next === tail) return null;
let first = head.next;
this.remove(first);
return first;
}
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const { cache, map } = this;
if (map.has(key)) {
let x = map.get(key);
cache.remove(x);
cache.addLast(x);
return map.get(key).val;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const { cache, map, size } = this;
const addRecently = function (key, value) {
let x = new Node(key, value);
cache.addLast(x);
map.set(key, x);
};
if (map.has(key)) {
let x = map.get(key);
cache.remove(x);
map.delete(key);
addRecently(key, value);
} else {
if (cache.size === this.capacity) {
let x = cache.removeFirst();
map.delete(x.k);
}
addRecently(key, value);
}
};
- Map 的巧妙使用 map 放入数据是按顺序的，最新放入的数据在迭代器最后 而且 map 的 entries 方法，还有 keys 方法，会返回一个迭代器，迭代器调用 next 也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.map = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const map = this.map;
let val = map.get(key);
if (val !== undefined) {
map.delete(key);
map.set(key, val);
return val;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const { map, capacity } = this;
if (map.has(key)) map.delete(key);
map.set(key, value);
if (map.size > capacity) {
map.delete(map.entries().next().value[0]);
}
};