[数据结构与算法]数据结构设计之LRU

LRU

思路

• 用map来维护key和value，将最近使用的键值对放在map的末尾。
• 为什么不用对象存储？因为对象中属性是没有顺序的(见文末的解释)。
• 无论是put还是get，都需要更新当前的key为最近使用。
  • 最简单的办法就是，先把key删除，再增加该key。
  • 由于Map查找key、删除key、增加key的时间复杂度都是O(1)，所以算法的整个时间复杂度为O(1)。

代码

/**
 * @param {number} capacity
 */


var LRUCache = function(capacity) {
    this.len = capacity;
    this.Cache = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */

LRUCache.prototype.get = function(key) {

    // if key不存在 => 返回-1
    if(!this.Cache.has(key)) return -1;
    // if key存在 => 删除该值并重新插入该键值对
    let val = this.Cache.get(key);
    this.Cache.delete(key);
    this.Cache.set(key, val);
    return val;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {

    // if key不存在 => 未达到上限 => 直接插入
    //                  达到上限 => 删除Map的第一个key，再插入这里的key。
    // if key存在 => 删除该key，重新插入该键值对。
    if(!this.Cache.has(key)){
        if(this.Cache.size>=this.len){
            this.Cache.delete(this.Cache.keys().next().value);
        }
    }else{
        this.Cache.delete(key)
    }
    this.Cache.set(key, value);

};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

关于ES6中Map对象和普通Object对象的区别

• Map对象的键可以为任何数据类型。而Object对象的键为字符串，如果加入的键为数字，也默认将其转换成字符串进行存储。
• Map对象的键值对遍历时和定义时顺序一致。而Chrome 的 JS 引擎遍历对象属性时会遵循一个规律： 它们会先提取所有 key 的 parseFloat 值为非负整数的属性，然后根据 数字顺序对属性排序首先遍历出来，然后按照 对象定义的顺序遍历余下的所有属性。
• 获取所有的键：mp.keys()返回迭代器，通过next().value获取键；Object.keys(obj)返回数组。