LRU 实现

LRU 概述

This algorithm requires keeping track of what was used when, which is expensive if one wants to make sure the algorithm always discards the least recently used item. General implementations of this technique require keeping “age bits” for cache-lines and track the “Least Recently Used” cache-line based on age-bits. – from Wikipedia

LRU 算法的思想是淘汰最近没有使用的缓存。

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

分析

和大部分存储解构一样，LRU 的存储能力是有限的，所以当缓存满的时候我们需要一种算法来淘汰一部分数据。LRU 故名思意就是淘汰掉最近没有被使用的缓存。

get 方法：如果元素不存在，直接返回 -1。如果元素存在，取出之后需要将当前元素移动到队列的头部。

put 方法：如果元素不存在，直接将元素添加到队列头部，如果元素存在，将元素移动到队列头部。

按照这个思路，可以使用队列实现 LRU，但是无论是基于链表还是基于数组的队列都无法同时在 O(1) 时间内完成 get 和 put 方法。

对于 JavaScript，如果使用 Map，添加元素的时候 map.keys() 会自动记录元素的添加顺序。基于这个特点，我们可以用 Map 轻松的实现 LRU

class LRUCache {
  constructor(capacity) {
    this.map = new Map();
    this.capacity = capacity;
  }

  get(key) {
    if(!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    }
    this.map.set(key, value);

    const keys = this.map.keys();
    while (this.map.size > this.capacity) {
      this.map.delete(keys.next().value);
    }
  }
}