https://github.com/sisterAn/JavaScript-Algorithms/issues/9

    Least recently used （最近最少使用）
    image.png

    1. /**
    2.  * @param {number} capacity
    3.  */
    4. var LRUCache = function (capacity) {
    5.     this.cache = new Map();
    6.     this.capacity = capacity; // 最大容量
    7. };
    9. /** 
    10.  * @param {number} key
    11.  * @return {number}
    12.  */
    13. LRUCache.prototype.get = function (key) {
    14.     let cache = this.cache;
    15.     if (cache.has(key)) {
    16.         let temp = cache.get(key)
    17.         cache.delete(key);
    18.         cache.set(key, temp);
    19.         return temp;
    20.     } else {
    21.         return -1;
    22.     }
    23. };
    25. /** 
    26.  * @param {number} key 
    27.  * @param {number} value
    28.  * @return {void}
    29.  */
    30. LRUCache.prototype.put = function (key, value) {
    31.     let cache = this.cache;
    32.     if (cache.has(key)) {
    33.         cache.delete(key);
    34.     } else if (cache.size >= this.capacity) {
    35.         cache.delete(cache.keys().next().value);
    36.     }
    37.     cache.set(key, value);
    38. };
    40. /**
    41.  * Your LRUCache object will be instantiated and called as such:
    42.  * var obj = new LRUCache(capacity)
    43.  * var param_1 = obj.get(key)
    44.  * obj.put(key,value)
    45.  */
    • get：访问某key，访问完要将其放在最后的。若key存在，先保存value值，删除key，再添加key，最后返回保存的value值。若key不存在，返回-1
    • put：新加一个key，要将其放在最后的。所以，若key已经存在，先删除，再添加。如果容量超出范围了，将map中的头部删除。
    • map.keys()返回一个迭代器
    • 这个迭代器调用next()方法，返回包含迭代器返回的下一个值，存在value属性中

    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

    LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
    LRU缓存 - 图2