华为&leetcode146：LRU 缓存机制

[sisterAn]

运用你所掌握的数据结构，设计和实现一个 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

[BoswellJi]

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);

[Lostsory]

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)
      }
    }
  }
}

[liwuhou]

感觉对象数组应该挺好实现的，每次调用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;
        }
    }
}

[uuRRx0]

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;
}

[sisterAn]

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

类 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

[BruceYuj]

有定期在 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

[zero9527]

/**
 * 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

[consoles]

看了下 所有的实现，基本上要么是基于数组的维护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());

[george-wq]

var LRUCache = function(num) {
this.maxNum = num ? num : 2;
this.data = new Map();
}
LRUCache.prototype.get = function(key) {
let value = -1;
if (this.data.get(key)) {
value = this.data.get(key);
this.data.delete(key);
this.put(key, value);
}
return value;
}
LRUCache.prototype.put = function(key, value) {
if (this.data.size === this.maxNum || this.data.get(key)) {
// this.data.delete([...this.data.keys()][0]);
this.data.delete(this.data.keys().next().value);
}
this.data.set(key,value);
}
var cache = new LRUCache(4);

[zjhlaap]

 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;
        }
      }
    }

[WalterBrightHub]

双向链表+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)
        }
    }
}