LRU
最近最少使用算法，操作系统中典型的Cache替换算法
146. LRU 缓存
方法一
循环双链表+map
规则如下
插入时，若key存在，更新值，并把节点移动到链表尾部
插入时，key不存在，若未达到capacity最大值，放入链表尾部
插入时，key不在，若达到capacity最大值，删除链表头部，插入链表尾部
获取值时，若不存在，直接返回-1
若值存在，把节点移动到尾部，然后返回对应值
function Link(key, val){
this.val = val
this.key = key
this.next = null
this.prior = null
}
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity
this.map = new Map()
this.size = 0
this.head = new Link(0,0)
this.head.next = this.head
this.head.prior = this.head
};
LRUCache.prototype.moveToTail = function(node){
if(node !== this.head.prior){
// delete
node.next.prior = node.prior
node.prior.next = node.next
// append
node.next = this.head
node.prior = this.head.prior
this.head.prior.next = node
this.head.prior = node
}
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if(!this.map.has(key)){
return -1
}
let node = this.map.get(key)
this.moveToTail(node)
return node.val
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if(this.map.has(key)){
let node = this.map.get(key)
node.val = value
this.moveToTail(node)
}else{
let node = new Link(key, value)
this.map.set(key, node)
// append
node.next = this.head
node.prior = this.head.prior
this.head.prior.next = node
this.head.prior = node
if(this.size >= this.capacity){
let key = this.head.next.key
this.map.delete(key)
// delete front
this.head.next.next.prior = this.head
this.head.next = this.head.next.next
}else{
this.size++
}
}
};
方法二
js的Map有个特点，Map.prototype.keys()的遍历顺序就是插入顺序,可以替代方法一中的循环双链表
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity
this.map = new Map()
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if(!this.map.has(key)){
return -1
}
let val = this.map.get(key)
this.map.delete(key)
this.map.set(key, val)
return val
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if(this.map.has(key)){
this.map.delete(key)
}
this.map.set(key, value)
if(this.map.size > this.capacity){
this.map.delete(this.map.keys().next().value)
}
};
方法三
计数模拟
规则如下
get或者put命中时，计数器清零，比其低的计数器加一，其余不变
put未命中且而含有空闲，计数器置为0，其余全加1
put未命中，且空间满时，淘汰掉计数值为capacity-1的块，新的块计数器置0，其余全加一