LRU缓存机制

[Cosen95]

LRU缓存机制：https://leetcode-cn.com/problems/lru-cache/

[Cosen95]

思路分析

基于ES6 Map中keys的有序性来实现

一个Map对象在迭代时会根据对象中元素的插入顺序来进行

• get操作 如果元素存在，先delete再set, 元素便会置为最新使用；如果不存在，返回-1

• put操作

  • 如果元素存在，先delete再set, 元素便会置为最新使用；
  • 如果容器超限，进行删除末尾元素操作，使用 Map{}.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) {
    let val = this.map.get(key)
    if(typeof val === 'undefined') return -1
    // 找到了更新顺序
    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)
    let keys = this.map.keys()
    while (this.map.size > this.capacity) {
    // 如果容器超限，进行删除末尾元素操作，使用 `Map{}.keys().next()`得到迭代器的第一个元素，为使用时间最远的元素，进行删除
        this.map.delete(keys.next().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)
 */