华为&leetcode146：LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 ( key ) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1 。
写入数据 put(key, value) - 如果密钥不存在，则写入数据。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据，从而为新数据留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

附leetcode地址：leetcode

function LRU(max) {
  this.max = max;
  this.cache = new Map();
}

LRU.prototype = {
  get(key) {
    const { cache } = this,
      value = cache.get(key);
    if (!value) return;
    cache.delete(key);
    cache.set(key, value);
    return value;
  },
  add(key, value) {
    const { cache } = this;
    if (cache.size > this.max - 1) {
      const keys = cache.keys().next().value;
      cache.delete(keys);
    }
    cache.set(key, value);
  }
};

const lru = new LRU(4);
lru.add(1, 1);
lru.add(2, 2);
lru.add(3, 3);
lru.add(4, 4);
lru.get(2);
lru.get(2);
lru.get(2);
lru.add(5, 5);

console.log(lru.cache);

class LRUCache {
  constructor(max) {
    this.max = max
    this.keys = []
    this.cache = {}
  }
  get = (k) => {
    if (this.cache[k]) {
      this.remove(this.keys, k)
      this.keys.push(k)
      return this.cache[k]
    } else {
      return -1
    }
  }
  put = (k, v) => {
    if (this.cache[k]) return
    this.keys.push(k)
    if (this.keys.length > this.max) {
      delete this.cache[this.keys[0]]
      this.keys.shift()
    }
    this.cache[k] = v
  }
  remove = (arr, item) => {
    if (arr.length) {
      const index = arr.indexOf(item)
      if (index > -1) {
        return arr.splice(index, 1)
      }
    }
  }
}

感觉对象数组应该挺好实现的，每次调用get方法获取数据或者put方法更新数据，都会将数据队列顺序都更新了，需要注意的是，put方法，需要判断当前队列长度是否超过缓存容量长度、是否是队列中已有的key这些问题，然后做对应操作。
这一切都是基于我理解的这个put方法应该是可以更新原有数据的。

class LRUCache{
    constructor(max){
        this.max = max;
        this.stack = [];
    }

    // 当前队列的长度
    get __length(){
        return this.stack.length;
    }
    
    // 查找元素下标
    _findIdx(key){
        const {stack} = this;
        for(let i=0; i<stack.length; i++){
            if(stack[i].key === key){
                return i;
            }
        }
        return -1;
    }

    // 末尾追加元素
    _push(key, value){
        this.stack.push({key, value});
    }
	
    // 访问数据
    get(key){
        const findIdx = this._findIdx(key);
        if(findIdx === -1) return -1;
        
        const [data] = this.stack.splice(findIdx, 1);
        this._push(data.key, data.value);
        return data.value;
    }
    
    // 增加数据
    put(key, value){
        const findIdx = this._findIdx(key);

        if(findIdx === -1){ // 元素不存在
            if(this.__length < this.max){ // 新增
                this._push(key, value);
            }else{ // 缓存容量将要溢出
                // 去掉最久未访问的元素
                const {key: delKey} = this.stack.shift();
                console.log(`该操作会使得密钥 ${delKey} 作废`)
                // 将最新的数据追加
                this._push(key, value);
            }
        }else{ // 元素存在，更新
            this.stack.splice(findIdx, 1);
            this._push({key, value})
        }
    }
}


// 测试
const cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

感觉自己想得有些复杂了，多搞个变量来存放key不就好了

class LRUCache{
    constructor(max){
        this.max = max;
        this.keys = [];
        this.data = {};
    }

    get __length(){
        return this.keys.length;
    }

    $find(key){
        return this.keys.indexOf(key);
    }

    get(key){
        const findIdx = this.$find(key);
        if(findIdx === -1) return -1;

        this.keys.push(this.keys.splice(findIdx, 1));
        return this.data[key]
    }

    put(key, value){
        const findIdx = this.$find(key);
        if(findIdx === -1){
            if(this.__length === this.max){
                const delKey = this.keys.shift();
                delete this.data[delKey];
                console.log(`该操作会使得密钥 ${delKey} 作废`);
            }
            this.keys.push(key);
            this.data[key] = value;
        }else{ // 更新
            this.keys.push(this.keys.splice(findIdx, 1));
            this.data[key] = value;
        }
    }
}

function LRUCache(n) {
    this.arr = Array(n);
    this.put = function (key, value) {
        var obj = {};
        obj[key] = value;
        this.arr.length >= this.maxlength && this.arr.pop();
        this.arr.unshift(obj);
    }
    this.get = function (key) {
        var index = this.arr.findIndex(ele => ele[key]);
        if(index === -1) return index;
        this.arr.unshift(this.arr.splice(index, 1)[0]);
        return this.arr[0][key];
    }
    this.maxlength = n;
}

function LRUCache(n) {
    this.map = new Map();
    this.put = function (key, value) {
        this.map.delete(key);
        this.map.set(key, value);
        this.map.size > this.maxSize && this.map.delete(this.map.keys().next().value);
    }
    this.get = function (key) {
        if(!this.map.has(key)) return -1;
        var temp = this.map.get(key);
        this.map.delete(key) && this.map.set(key, temp);
        return temp;
    }
    this.maxSize = n;
}

基础解法：数组+对象实现

类 vue keep-alive 实现

var LRUCache = function(capacity) {
    this.keys = []
    this.cache = Object.create(null)
    this.capacity = capacity
};

LRUCache.prototype.get = function(key) {
    if(this.cache[key]) {
        // 调整位置
        remove(this.keys, key)
        this.keys.push(key)
        return this.cache[key]
    }
    return -1
};

LRUCache.prototype.put = function(key, value) {
    if(this.cache[key]) {
        // 存在即更新
        this.cache[key] = value
        remove(this.keys, key)
        this.keys.push(key)
    } else {
        // 不存在即加入
        this.keys.push(key)
        this.cache[key] = value
        // 判断缓存是否已超过最大值
        if(this.keys.length > this.capacity) {
            removeCache(this.cache, this.keys, this.keys[0])
        }
    }
};

// 移除 key
function remove(arr, key) {
    if (arr.length) {
        const index = arr.indexOf(key)
        if (index > -1) {
            return arr.splice(index, 1)
        }
    }
}

// 移除缓存中 key
function removeCache(cache, keys, key) {
    cache[key] = null
    remove(keys, key)
}

进阶：Map

利用 Map 既能保存键值对，并且能够记住键的原始插入顺序

var LRUCache = function(capacity) {
    this.cache = new Map()
    this.capacity = capacity
}

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // 存在即更新
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
    return -1
}

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // 存在即更新（删除后加入）
        this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
        // 不存在即加入
        // 缓存超过最大值，则移除最近没有使用的
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
}

leetcode

有定期在 github 更新 leetcode 和其他 OI 里面的题目。欢迎各位 watch 讨论（不用star）。
主要语言为 JavaScript，偶尔会用 Python 或 Java
JavaScript 版 LeetCode 题解
 我的 LeetCode 地址
下面给出 JavaScript 版本

/**
 * @param {number} capacity
 */var LRUCache = function(capacity) {
  this.cache = new Map();
  this.capacity = capacity;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  let cache = this.cache;
  if (cache.has(key)) {
    // 如果有就删了重新插入，保证是新的插在最后面
    let temp = cache.get(key);
    cache.delete(key);
    cache.set(key, temp);
    return temp;
  } else {
    return -1;
  }
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  let cache = this.cache;
  if (cache.has(key)) {
    // 同get
    cache.delete(key);
  } else if (cache.size >= this.capacity) {
    // 缓存已满时，cache.keys().next()返回最开始插入的
    cache.delete(cache.keys().next().value);
  }
  cache.set(key, value);
};

思路

在操作系统中， LRU 是一种常用的页面置换算法。其目的在于在发生缺页中断时，将最长时间未使用的页面给置换出去。因此，我们需要算法中的效率足够的高。
由题目可以知道，整个算法会包含以下几个操作：

get(key): 在 $O(1)$ 时间内获取对应的值。很明显，支持常数时间存取的哈希表符合我们的要求
put(key, value): 在 $O(1)$ 时间内存储对应的键值对，如果当前缓存中已经有对应的 key，则直接更新 value，并且将位置放到最近使用的地方。而在常数时间里面交换值和删除值的数据结构就是链表了。
move_to_tail(): 将当前键值对移到尾部。

从上面分析来看，哈希表+双向链表就是 LRU 缓存算法的核心数据结构了。我们使用链表尾部结点来表示最近访问的结点。

细心的读者可能会产生疑问，为什么使用双向链表而不是单向链表？
原因在于，如果想要在常数时间内将链表中间的结点移动到尾部，我们需要能够在 $O(1)$ 时间内获得当前结点的前驱结点。

首先，我们设计链表的结点：

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

细心的读者会发现，我们在设计结点的时候重复存储了 key（哈希表和双向链表中都存储了 key），这又是为什么呢？
这是因为我们在缓存满时需要删除双向链表中的结点以及结点在哈希表中保存的值。如果不在哈希表中存储 key，就无法在哈希表中进行对应的删除了。

代码

class ListNode:
    def __init__(self, key=None, value=None):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        # 新建两个节点 head 和 tail
        self.head = ListNode()
        self.tail = ListNode()
        # 初始化链表为 head <-> tail
        self.head.next = self.tail
        self.tail.prev = self.head

    # get 和 put 操作可能都会调用 move_to_tail 方法
    def move_to_tail(self, key):
        node = self.hashmap[key]
        # 将 node 结点的前驱结点和后驱结点相连
        node.prev.next = node.next
        node.next.prev = node.prev
        # 将 node 插入到尾节点前
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def get(self, key: int) -> int:
        if key in self.hashmap:
            # 如果已经在链表中了久把它移到末尾（变成最新访问的）
            self.move_to_tail(key)
            return self.hashmap.get(key).value

        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.hashmap:
            # 如果 key 本身已经在哈希表中了就不需要在链表中加入新的节点
            # 但是需要更新字典该值对应节点的 value
            self.hashmap[key].value = value
            # 之后将该节点移到末尾
            self.move_to_tail(key)
        else:
            if len(self.hashmap) == self.capacity:
                # 去掉哈希表对应项
                self.hashmap.pop(self.head.next.key)
                # 去掉最久没有被访问过的节点，即头节点之后的节点
                self.head.next = self.head.next.next
                self.head.next.prev = self.head
            # 将新结点插入到尾节点前
            newNode = ListNode(key, value)
            self.hashmap[key] = newNode
            newNode.prev = self.tail.prev
            newNode.next = self.tail
            self.tail.prev.next = newNode
            self.tail.prev = newNode

/**
 * leetcode
 * LRU 缓存机制算法
 * @param {*} maxlength
 */
function LRU(maxlength) {
  this.maxLength = maxlength;
  this.cache = [];
}

LRU.prototype = {
  constructor: LRU,
  get: function (key) {
    const index = this.findIndex(key);
    // 移动到最前面
    if (index !== -1) {
      const item = this.cache[index];
      this.cache.splice(index, 1);
      this.cache.unshift(item);
      delete item;
      return this.cache[0].value;
    }
    return -1;
  },
  put: function (key, value) {
    const index = this.findIndex(key);
    if (index !== -1) this.cache.splice(index, 1);
    this.cache.unshift({ key, value });
    this.remove();
  },
  findIndex: function (key) {
    return this.cache.findIndex((item) => item.key === key);
  },
  remove: function () {
    if (this.cache.length > this.maxLength) {
      this.cache.pop();
    }
  },
};

const cache = new LRU(2);

cache.put(1, 1);
cache.put(2, 2);
console.log('cache.get(1): ', cache.get(1)); // 返回  1
cache.put(3, 3); // 该操作会使得密钥 2 作废
console.log('cache.get(2): ', cache.get(2)); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
console.log('cache.get(1): ', cache.get(1)); // 返回 -1 (未找到)
console.log('cache.get(3): ', cache.get(3)); // 返回  3
console.log('cache.get(4): ', cache.get(4)); // 返回  4

看了下所有的实现，基本上要么是基于数组的维护key的顺序（这需要O（n）的时间找到key所在的索引），要么依赖map本身能维护插入的顺序：访问的时候key的时候删除key重新加入key，这样这个key就在末尾了最后被淘汰，之前写了个基于双向链表 + 哈希表的，这里提供一个思路：

class Node {
  constructor(value, prev, next) {
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

class DoubleLinkedList {

  constructor() {
    this.head = null;
    this.tail = null;
  }

  insertFirst(value) {
    if (!this.head) {
      this.head = this.tail = new Node(value);
    } else {
      const newNode = new Node(value, null, this.head);
      this.head.prev = newNode;
      this.head = newNode;
    }
    return this.head;
  }

  deleteLast() {
    if (!this.tail) return null;

    const ret = this.tail;

    const newTail = this.tail.prev;

    if (!newTail) {
      this.head = null;
    } else {
      newTail.next = null;
    }

    return ret.value;
  }

  // 把节点移动到头部
  moveToFront(node) {
    if (!node || node === this.head) return; // 已经在头部了
    const {prev, next} = node;
    // 这个判断其实没有必要，因为前面已经判断过不是头结点了，前驱节点一定存在,写这个的目的是
    if (prev) {
      prev.next = next;
    }
    if (next) {
      next.prev = prev;
    }
    node.prev = null;
    node.next = this.head;

    this.head.prev = node;
    this.head = node;
  }

}

class LRU {

  constructor() {
    this.list = new DoubleLinkedList();
    this.map = new Map(); // key => 元素 ；value，双向链表中的节点
  }

  /**
   * 将不存在数据结构中的元素插入
   * @param value
   */
  access(value) {
    let node = this.map.get(value);
    if (!node) {
      node = this.list.insertFirst(value);
      this.map.set(value, node);
    } else {
      this.list.moveToFront(node);
    }
  }

  /**
   * 删除并返回最近最少访问的元素
   */
  delete() {
    const value = this.list.deleteLast();
    this.map.delete(value);
    return value;
  }

  toString() {
    let cur = this.list.head;
    const values = [];
    while (cur) {
      values.push(cur.value);
      cur = cur.next;
    }
    return values.join(' -> ');
  }
}

const cache = new LRU();

cache.access(7);
console.log(cache.toString());
cache.access(0);
console.log(cache.toString());
cache.access(1);
console.log(cache.toString());
cache.access(2);
console.log(cache.toString());
cache.access(0);
console.log(cache.toString());
cache.access(3);
console.log(cache.toString());
cache.access(0);
console.log(cache.toString());
console.log('delete last',cache.delete());
console.log(cache.toString());
cache.access(4);
console.log(cache.toString());

 class LRUCache {
      constructor(maxCache) {
        this.maxCache = maxCache;
        this.keys = [];
      }
      put(key, value) {
        const index = this.keys.findIndex(item => item.key === key);
        if (index === -1) {
          if (this.keys.length >= this.maxCache) this.keys.splice(0, 1);
        } else this.keys.splice(index, 1)
        this.keys.push({
          key,
          value
        })
      }
      get(key) {
        const index = this.keys.findIndex(item => item.key === key);
        if (index === -1) return -1;
        else {
          const deleteItem = this.keys.splice(index, 1);
          this.keys.push(deleteItem[0]);
          return deleteItem[0].value;
        }
      }
    }

双向链表+Map

class LRUCache{
    cache=new Map()
    capacity
    head={}                         //head表示最少访问
    constructor(capacity){
        this.capacity=capacity
        this.link(this.head,this.head)
    }
    link(nodeA,nodeB){
        nodeA.next=nodeB
        nodeB.prev=nodeA
    }
    moveToTail(cache_at_key){       //tail表示最近访问
        //优化：连续访问时无需操作
        if(cache_at_key.next===this.head) return;
        this.link(cache_at_key.prev,cache_at_key.next)
        let tail_prev_node=this.head.prev
        this.link(tail_prev_node,cache_at_key)
        this.link(cache_at_key,this.head)
    }
    get(key){
        let cache_at_key=this.cache.get(key)
        if(cache_at_key){
            //命中，放到最近访问
            this.moveToTail(cache_at_key)
            return cache_at_key.value
        }
        else{
            return -1
        }
    }
    put(key,value){
        let cache_at_key=this.cache.get(key)
        if(cache_at_key){
            cache_at_key.value=value
            //命中，放到最近访问
            this.moveToTail(cache_at_key)
        }
        else{                
            if(this.cache.size===this.capacity){
                let lru_node=this.head.next
                this.link(this.head,lru_node.next)
                //淘汰LRU
                this.cache.delete(lru_node.key)
            }
            //创建节点，并放到最近访问
            this.cache.set(key,{value,key})
            let cache_at_key=this.cache.get(key)
            this.link(this.head.prev,cache_at_key)
            this.link(cache_at_key,this.head)
        }
    }
}

// 移除缓存中 key
function removeCache(cache, keys, key) {
    cache[key] = null
    remove(keys, key)
}

这里应该要 delete cache[key] 吧

class LRUCahce {
  constructor(capacity) {
    this.cahce = new Map()
    this.capacity = capacity
  }

  get(key) {
    if (this.cache.has(key)) {
      const temp = this.cache.get(key)
      this.cache.delete(key)
      this.cache.set(key, temp)
      return temp
    }
    return -1
  }

  put(key, value) {
    if(this.cahce.has(key)) {
      this.cache.delete(key)
    }else if(this.cache.size === this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }

    this.cache.set(key, value)
  }
}

@PARAM

/**

@PARAM {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity=capacity;
this.save=new Map();
this.clear=function(){
while(this.save.size>=this.capacity){
this.save.delete(this.save.keys().next().value)
}
}
};

/**

@PARAM {number} key
@return {number}
*/
LRUCache.prototype.get = function(key) {
if(this.save.has(key)){
var val=this.save.get(key);
this.save.delete(key)
this.save.set(key,val)
return val
}
return -1
};

/**

@PARAM {number} key
@PARAM {number} value
@return {void}
*/
LRUCache.prototype.put = function(key, value) {
if(this.save.has(key)){
this.save.delete(key)
this.save.set(key,value)
}else{
this.clear();
this.save.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)
*/

借助javascript Map的特性：map的键是按照set的顺序存储的。
MDN Map.prototype.keys()

var LRUCache = function(capacity) {
    this.cache = new Map()
    this.capacity = capacity
}

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // 存在即更新
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
    return -1
}

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // 存在即更新（删除后加入）
        this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
        // 不存在即加入
        // 缓存超过最大值，则移除最近没有使用的
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
}

基础解法：数组+对象实现

类 vue keep-alive 实现

var LRUCache = function(capacity) {
    this.keys = []
    this.cache = Object.create(null)
    this.capacity = capacity
};

LRUCache.prototype.get = function(key) {
    if(this.cache[key]) {
        // 调整位置
        remove(this.keys, key)
        this.keys.push(key)
        return this.cache[key]
    }
    return -1
};

LRUCache.prototype.put = function(key, value) {
    if(this.cache[key]) {
        // 存在即更新
        this.cache[key] = value
        remove(this.keys, key)
        this.keys.push(key)
    } else {
        // 不存在即加入
        this.keys.push(key)
        this.cache[key] = value
        // 判断缓存是否已超过最大值
        if(this.keys.length > this.capacity) {
            removeCache(this.cache, this.keys, this.keys[0])
        }
    }
};

// 移除 key
function remove(arr, key) {
    if (arr.length) {
        const index = arr.indexOf(key)
        if (index > -1) {
            return arr.splice(index, 1)
        }
    }
}

// 移除缓存中 key
function removeCache(cache, keys, key) {
    cache[key] = null
    remove(keys, key)
}

进阶：Map

利用 Map 既能保存键值对，并且能够记住键的原始插入顺序

var LRUCache = function(capacity) {
    this.cache = new Map()
    this.capacity = capacity
}

LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        // 存在即更新
        let temp = this.cache.get(key)
        this.cache.delete(key)
        this.cache.set(key, temp)
        return temp
    }
    return -1
}

LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        // 存在即更新（删除后加入）
        this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
        // 不存在即加入
        // 缓存超过最大值，则移除最近没有使用的
        this.cache.delete(this.cache.keys().next().value)
    }
    this.cache.set(key, value)
}

leetcode

第一种方法里面，if(this.cache[key])如果值正好是0就有问题了呢~

题目地址(146. LRU 缓存机制)

https://leetcode-cn.com/problems/lru-cache/

题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。

实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

思路

确定需要使用的数据结构
1. 根据题目要求,存储的数据需要保证顺序关系(逻辑层面) ===> 使用数组,链表等保证顺序关系
2. 同时需要对数据进行频繁的增删, 时间复杂度 O(1) ==> 使用链表等
3. 对数据进行读取时, 时间复杂度 O(1) ===> 使用哈希表
  最终采取双向链表 + 哈希表
  1. 双向链表按最后一次访问的时间的顺序进行排列, 链表头部为最近访问的节点
  2. 哈希表,以关键字为键,以链表节点的地址为值
put 操作
通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
1. 如果存在,
  1. 将该链表节点的值更新
  2. 将该该链表节点调整至链表头部
2. 如果不存在
  1. 如果链表容量未满,
    1. 新生成节点,
    2. 将该节点位置调整至链表头部
  2. 如果链表容量已满
    1. 删除尾部节点
    2. 新生成节点
    3. 将该节点位置调整至链表头部
  3. 将新生成的节点，按关键字为键，节点地址为值插入哈希表
get 操作
通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
1. 节点存在
  1. 将该节点位置调整至链表头部
  2. 返回该节点的值
2. 节点不存在, 返回 null

伪代码如下：

var LRUCache = function(capacity) {
	保存一个该数据结构的最大容量
	生成一个双向链表,同时保存该链表的头结点与尾节点
	生成一个哈希表
};

function get (key) {
	if 哈希表中存在该关键字 {
		根据哈希表获取该链表节点
		将该节点放置于链表头部
		return 链表节点的值
	} else {
		  return -1
	}
};

function put (key, value) {
    if 哈希表中存在该关键字 {
		根据哈希表获取该链表节点
		将该链表节点的值更新
		将该节点放置于链表头部
	} else {
		if 容量已满 {
			删除链表尾部的节点
			新生成一个节点
			将该节点放置于链表头部
		} else {
			新生成一个节点
			将该节点放置于链表头部
		}
	}
};

代码

语言支持: JS, Go, PHP, CPP

JS Code:

function ListNode(key, val) {
  this.key = key;
  this.val = val;
  this.pre = this.next = null;
}

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.size = 0;
  this.data = {};
  this.head = new ListNode();
  this.tail = new ListNode();
  this.head.next = this.tail;
  this.tail.pre = this.head;
};

function get(key) {
  if (this.data[key] !== undefined) {
    let node = this.data[key];
    this.removeNode(node);
    this.appendHead(node);
    return node.val;
  } else {
    return -1;
  }
}

function put(key, value) {
  let node;
  if (this.data[key] !== undefined) {
    node = this.data[key];
    this.removeNode(node);
    node.val = value;
  } else {
    node = new ListNode(key, value);
    this.data[key] = node;
    if (this.size < this.capacity) {
      this.size++;
    } else {
      key = this.removeTail();
      delete this.data[key];
    }
  }
  this.appendHead(node);
}

function removeNode(node) {
  let preNode = node.pre,
    nextNode = node.next;
  preNode.next = nextNode;
  nextNode.pre = preNode;
}

function appendHead(node) {
  let firstNode = this.head.next;
  this.head.next = node;
  node.pre = this.head;
  node.next = firstNode;
  firstNode.pre = node;
}

function removeTail() {
  let key = this.tail.pre.key;
  this.removeNode(this.tail.pre);
  return key;
}

Go Code:

type LRUCache struct {
	Cap   int
	Hash  map[int]*DoubleListNode
	Cache *DoubleList
	Size  int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		Cap:   capacity,
		Hash:  make(map[int]*DoubleListNode),
		Cache: NewDoubleList(),
	}
}

func (this *LRUCache) Get(key int) int {
	n, ok := this.Hash[key]
	if !ok {
		return -1
	}

	// 设为最近使用过
	this.Cache.remove(n)
	this.Cache.append(n)

	return n.Val
}

func (this *LRUCache) Put(key int, value int) {
	n, ok := this.Hash[key]
	if !ok { // cache 不存在
		// 增加节点
		newNode := &DoubleListNode{Key: key, Val: value}
		this.Hash[key] = newNode
		this.Cache.append(newNode)

		if this.Cap == this.Size { // 已满
			// 删除尾节点
			tailNode := this.Cache.tail.Pre
			delete(this.Hash, tailNode.Key)
			this.Cache.remove(tailNode)
		} else {
			this.Size++
		}
	} else {
		// cache 存在
		// 设为最近使用过
		this.Cache.remove(n)
        this.Cache.append(n)

        n.Val = value // 更新值
	}
}

type DoubleListNode struct {
	Key, Val  int
	Pre, Next *DoubleListNode
}

type DoubleList struct {
	Head, tail *DoubleListNode
}

func NewDoubleList() *DoubleList {
	dl := &DoubleList{
		Head: &DoubleListNode{},
		tail: &DoubleListNode{},
	}
	dl.Head.Next = dl.tail
	dl.tail.Pre = dl.Head
	return dl
}

func (dl *DoubleList) append(n *DoubleListNode) {
	n.Next = dl.Head.Next
	n.Pre = dl.Head
	dl.Head.Next.Pre = n
	dl.Head.Next = n
}

func (dl *DoubleList) remove(n *DoubleListNode) {
	n.Pre.Next = n.Next
	n.Next.Pre = n.Pre
}

PHP Code:

class LRUCache
{
    public $hash = []; // key => DoubleListNode
    public $cache;
    public $size = 0;
    public $cap; // 容量

    /**
     * @param Integer $capacity
     */
    function __construct($capacity)
    {
        $this->cap = $capacity;
        $this->cache = new DoubleList();
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key)
    {
        if (!isset($this->hash[$key])) return -1;

        // 更新节点
        /** @var DoubleListNode $node */
        $node = $this->hash[$key];
        $this->cache->remove($node);
        $this->cache->append($node);

        return $node->val;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value)
    {
        if (isset($this->hash[$key])) { // key 存在
            // 更新节点
            /** @var DoubleListNode $node */
            $node = $this->hash[$key];
            $this->cache->remove($node);
            $this->cache->append($node);
            $node->val = $value;
        } else { // key 不存在, 新增节点
            $node = new DoubleListNode($key, $value);
            $this->cache->append($node);
            $this->hash[$key] = $node;

            if ($this->size == $this->cap) {
                // 删除原节点
                $oldNode = $this->cache->tail->pre;
                $this->cache->remove($oldNode);
                unset($this->hash[$oldNode->key]);
            } else {
                $this->size++;
            }
        }
    }
}

class DoubleListNode
{
    public $key;
    public $val;
    public $pre;
    public $next;

    public function __construct($key = null, $val = null)
    {
        if ($key) $this->key = $key;
        if ($val) $this->val = $val;
    }
}

class DoubleList
{
    public $head;
    public $tail;

    public function __construct()
    {
        $this->head = new DoubleListNode();
        $this->tail = new DoubleListNode();
        $this->head->next = $this->tail;
        $this->tail->pre = $this->head;
    }

    public function append(DoubleListNode $node)
    {
        $node->pre = $this->head;
        $node->next = $this->head->next;
        $this->head->next->pre = $node;
        $this->head->next = $node;
    }

    public function remove(DoubleListNode $node)
    {
        $node->pre->next = $node->next;
        $node->next->pre = $node->pre;
    }
}

CPP Code:

class LRUCache {
private:
  list<pair<int, int>> data;
  unordered_map<int, list<pair<int, int>>::iterator> m;
  int capacity;
public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    if (!m.count(key)) return -1;
    data.splice(data.begin(), data, m[key]);
    m[key] = data.begin();
    return data.front().second;
  }

  void put(int key, int value) {
    if (get(key) == -1) {
      if (data.size() == capacity) {
        auto p = data.back();
        m.erase(p.first);
        data.pop_back();
      }
      data.emplace_front(key, value);
      m[key] = data.begin();
    } else data.front().second = value;
  }
};

复杂度分析

时间复杂度：$O(1)$
空间复杂度：$O(n)$ n 为容量的大小

class LRUCache {
    constructor (size) {
        this.size = size;
        this.caches = new Map()
    }

    put (key,val) {
        if (this.caches.size >= this.size) {
             this.caches.delete(this.caches.keys().next().value)
             this.caches.set(key,val) 
        } else {
             this.caches.set(key,val) 
        }
           
    }

    get (key) {
        if (this.caches.has(key)) {
            let temp = this.caches.get(key)
            this.caches.delete(key)
            this.caches.set(key,temp) 
            return this.caches.get(key)
        } else {
            return -1;
        }
    }
}

class LRUCache{
    constructor(cacheVolume){
        this.cache = []
        this.cacheLen = cacheVolume
        this.cacheIndex = 0
    }

    put(key, value){
        if (this.cacheIndex == this.cacheLen){
            this.cache.shift()
        }else{
            this.cacheIndex ++
        }
        
        this.cache.push({
            [key]: value
        })
    }

    get(key){
        let item = this.cache.find(item => key in item)

        if (item !== undefined){
            let index = this.cache.indexOf(item)

            this.cache.splice(index, 1)

            this.cache.push(item)

            return item[key]
        }
        
        return -1


    }
}

function LRU(max) {
  this.max = max;
  this.cache = new Map();
}

LRU.prototype = {
  get(key) {
    const { cache } = this,
      value = cache.get(key);
    if (!value) return;
    cache.delete(key);
    cache.set(key, value);
    return value;
  },
  add(key, value) {
    const { cache } = this;
    if (cache.size > this.max - 1) {
      const keys = cache.keys().next().value;
      cache.delete(keys);
    }
    cache.set(key, value);
  }
};

const lru = new LRU(4);
lru.add(1, 1);
lru.add(2, 2);
lru.add(3, 3);
lru.add(4, 4);
lru.get(2);
lru.get(2);
lru.get(2);
lru.add(5, 5);

console.log(lru.cache);

add 也属于操作数据，所以每次都要更新下缓存，在 if (cache.size > this.max - 1) {之前判断下cache.has(key),然后从cache中删除

class LRUCache {
  constructor(max) {
    this.map = new Map()
    this.max = max;
  }
  get (k) {
    if (this.map.has(k)) {
      var v = this.map.get(k)
      this.map.delete(k)
      this.map.set(k, v)
      return this.map.get(k)
    }
    return -1
  }
  put(k, v) {
    this.map.set(k, v)
    if (this.map.size > this.max){
      var fk = this.map.keys().next().value;
      if (fk) {
        this.map.delete(fk)
      }
    }
  }
}

class LRUCache {
    max: number
    map: Map<number, number> = new Map()
    constructor(capacity: number) {
        this.max = capacity
        this.map = new Map()
    }

    get(key: number): number {
        if (this.map.has(key)) {
            let value = this.map.get(key)
            this.map.delete(key)
            this.map.set(key, value)
            return value 
        } else {
            return -1
        }
    }

    put(key: number, value: number): void {
        if (this.map.has(key)) {
            this.map.delete(key)
            this.map.set(key, value)
        } else {
            if (this.map.size === this.max) {
                let firstKey = this.map.keys().next().value;
                this.map.delete(firstKey);
            }
            this.map.set(key, value)
        }
    }
}

class LinkNode {
                constructor(key, value) {
                    this.key = key
                    this.value = value
                    this.prev = null
                    this.next = null
                }
            }
            class LRUCache {
                constructor(capacity) {
                    this.cache = new Map()
                    this.capacity = capacity
                    this.head = null
                    this.tail = null

                    this.#init()
                }
                #init() {
                    this.head = new LinkNode()
                    this.tail = new LinkNode()
                    this.head.next = this.tail
                    this.tail.prev = this.head
                }

                get(key) {
                    if (this.cache.has(key)) {
                        let node = this.cache.get(key)
                        this.#deleteNode(node)
                        this.#addNode(node)
                        return node.value
                    } else {
                        return -1
                    }
                }

                put(key, value) {
                    if (this.cache.has(key)) {
                        let node = this.cache.get(key)
                        node.value = value
                        this.#deleteNode(node)
                        this.#addNode(node)
                    } else {
                        let node = new LinkNode(key, value)
                        this.cache.set(key, node)
                        this.#addNode(node)
                        if (this.cache.size > this.capacity) {
                            let deleteKey = this.#deleteTailNode()
                            this.cache.delete(deleteKey)
                        }
                    }
                }

                #deleteTailNode() {
                    let key = this.tail.prev.key
                    this.#deleteNode(this.tail.prev)
                    this.cache.delete(key)
                    return key
                }

                #deleteNode(node) {
                    node.next.prev = node.prev
                    node.prev.next = node.next
                }
                #addNode(node) {
                    let firstNode = this.head.next
                    this.head.next = node
                    node.prev = this.head
                    node.next = firstNode
                    firstNode.prev = node
                }
            }

Navigation Menu

Repository navigation

华为&leetcode146：LRU 缓存机制 #7

思路

代码

题目地址(146. LRU 缓存机制)

题目描述

思路

代码

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

华为&leetcode146：LRU 缓存机制 #7

Description

Activity

BoswellJi commented on Apr 7, 2020

Lostsory commented on Apr 7, 2020

liwuhou commented on Apr 7, 2020

uuRRx0 commented on Apr 7, 2020

sisterAn commented on Apr 7, 2020

BruceYuj commented on Apr 8, 2020

思路

代码

zero9527 commented on Apr 28, 2020

consoles commented on May 2, 2020

george-wq commented on May 16, 2020

zjhlaap commented on Jun 3, 2020

WalterBrightHub commented on Jun 27, 2020

cutie6 commented on Jul 11, 2020

Been101 commented on Jul 13, 2020

Verahuan commented on Jul 22, 2020

AnranS commented on Nov 14, 2020

DbbHobo commented on Jan 8, 2021

azl397985856 commented on Mar 3, 2021

题目地址(146. LRU 缓存机制)

题目描述

思路

代码

RyanMeg123 commented on May 24, 2022

nekobaex commented on May 2, 2023

liuyu666 commented on May 31, 2023

AjaxSir commented on Aug 2, 2023

RainyNight9 commented on Sep 27, 2023

itouchzh commented on Apr 9, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions