Open shfshanyue opened 4 years ago
LRU (最近最少使用) 缓存机制
数组存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;
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)
}
}
可以借助
Map
实现