js实现LRU缓存机制

题目描述

思路编码

由于当前考虑时间复杂度在O(1)，且由于当进行缓存容量达到上限时，需删除最久未使用的数据值，因此我们需要一个有序的Hash结构，我们第一个反应便是通过Map来存储数据。这也是为什么要用Map而不是对象的原因（ps：对象key无序）。

说干就干

class LRUCache {
    constructor(capacity){
        this.capacity = capacity;
        this.cache = new Map();
    }
    
    get(key){
       const isHasKey = this.cache.has(key);
    
       if(!isHasKey){
           return -1;
       }else{
       const val = this.cache.get(key);
       
       // 此处需先删除再重新插入已更新使用顺序
       this.cache.delete(key);
       this.cache.set(key,val);
       
       return val;
       }
    }
    
    put(key,val){
       
        if(this.cache.size >= this.capacity){
            // 删除最久未使用key
            this.cache.delete(this.cache.keys().next().value)
        }
        
        const isHasKey = this.cache.has(key);
        // 存在时更新顺序
        if(isHasKey){
            this.cache.delete(key);
        }
        
        this.cache.set(key,val);
    }
}
复制代码

总结：
当我们看到题目中涉及时间度为O(1)且有序时 便可以往Map对象上去考虑?了。