关于前端:LRU算法

LRU 算法实际

使用你所把握的数据结构，设计和实现一个 LRU (最近起码应用) 缓存机制。它应该反对以下操作：获取数据 get 和写入数据 put。
获取数据 get(key) – 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是负数），否则返回 -1。
写入数据 put(key, value) – 如果密钥不存在，则写入数据。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据，从而为新数据留出空间。

function LRUCache(max){this.cacheList = new Map() // 利用 Map 的能够记录贮存程序，来记录缓存
  this.max = max // 设置能缓存的最大值
}
LRUCache.prototype.get = function(key) {
  /**
   *  判断以后 key 是否存在，如果存在 删除以后 key 键值对，同时在开端增加新的 key value
   *  放弃最近应用
   *  否则 没找到 返回 -1
   */
  if(this.cacheList.has(key)) {let value = this.cacheList.get(key)
    this.cacheList.delete(key)
    this.cacheList.set(key, value)
    return this.cacheList.get(key)
  } else {return -1}
}
LRUCache.prototype.put = function(key, value) {
  /**
   * 删除以后 key，如果存在，删除胜利返回 true
   * 设置新的 key,value
   * 否则 持续下一步
   */
  if(this.cacheList.delete(key)) {this.cacheList.set(key, value)
    return
  }
  /**
   * 如果 以后数组没有以后 key，则比拟以后缓存数量，和最大缓存数量比拟
   * 如果 还有缓存空间，间接增加 key value
   * 否则 移除最先增加项，而后增加 key value
   */
  if(this.cacheList.size < this.max) {this.cacheList.set(key, value)
  } else {let keys = [...this.cacheList.keys()]
    this.cacheList.delete(keys[0])
    this.cacheList.set(key, value)
  }
}

let cache = new LRUCache(2 /* 缓存容量 */);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1) );     // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
console.log(cache.get(2));      // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
console.log(cache.get(1));       // 返回 -1 (未找到)
console.log(cache.get(3));      // 返回  3
console.log(cache.get(4));       // 返回  4