介绍

LRU（The Least Recently Used，最近最久未使用算法）是一种常见的缓存算法，在很多分布式缓存系统（如 Redis, Memcached）中都有广泛使用。LRU 算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

LRU 算法的描述： 设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

• set (key,value)：将记录 (key,value) 插入该结构。当缓存满时，将最久未使用的数据置换掉。
• get (key)：返回 key 对应的 value 值。

实现：最朴素的思想就是用数组 + 时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+ 哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），在 Java 里有对应的数据结构 LinkedHashMap。

利用 Java 的 LinkedHashMap 用非常简单的代码来实现基于 LRU 算法的 Cache 功能。

class LRUCache extends LinkedHashMap<Integer,Integer>{
    private int capacity;
    public LRUCache(int capacity) {
        //调用父类中的构造方法创建一个LinkedHashMap，设置其容量为capacity，loadFactor为0.75，并开启accessOrder为true
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        //若key存在,返回对应value值;若key不存在,返回-1
        return super.getOrDefault(key,-1);
    }
    
    public void put(int key, int value) {
        super.put(key,value);
    }
    protected boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest){
        //若返回的结果为true，则执行removeEntryForKey方法删除eldest entry
        return size() > capacity;
    }
}

实现

JavaScript

class LRUCache {
  // LRU Cache to store a given capacity of data
  #capacity

  /**
   * @param {number} capacity - the capacity of LRUCache
   * @returns {LRUCache} - sealed
   */
  constructor (capacity) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new TypeError('Invalid capacity')
    }

    this.#capacity = ~~capacity
    this.misses = 0
    this.hits = 0
    this.cache = new Map()

    return Object.seal(this)
  }

  get info () {
    return Object.freeze({
      misses: this.misses,
      hits: this.hits,
      capacity: this.capacity,
      size: this.size
    })
  }

  get size () {
    return this.cache.size
  }

  get capacity () {
    return this.#capacity
  }

  set capacity (newCapacity) {
    if (newCapacity < 0) {
      throw new RangeError('Capacity should be greater than 0')
    }

    if (newCapacity < this.capacity) {
      let diff = this.capacity - newCapacity

      while (diff--) {
        this.#removeLeastRecentlyUsed()
      }
    }

    this.#capacity = newCapacity
  }

  /**
 * delete oldest key existing in map by the help of iterator
 */
  #removeLeastRecentlyUsed () {
    this.cache.delete(this.cache.keys().next().value)
  }

  /**
   * @param {string} key
   * @returns {*}
   */
  has (key) {
    key = String(key)

    return this.cache.has(key)
  }

  /**
   * @param {string} key
   * @param {*} value
   */
  set (key, value) {
    key = String(key)
    // Sets the value for the input key and if the key exists it updates the existing key
    if (this.size === this.capacity) {
      this.#removeLeastRecentlyUsed()
    }

    this.cache.set(key, value)
  }

  /**
   * @param {string} key
   * @returns {*}
   */
  get (key) {
    key = String(key)
    // Returns the value for the input key. Returns null if key is not present in cache
    if (this.cache.has(key)) {
      const value = this.cache.get(key)

      // refresh the cache to update the order of key
      this.cache.delete(key)
      this.cache.set(key, value)

      this.hits++
      return value
    }

    this.misses++
    return null
  }

  /**
   * @param {JSON} json
   * @returns {LRUCache}
   */
  parse (json) {
    const { misses, hits, cache } = JSON.parse(json)

    this.misses += misses ?? 0
    this.hits += hits ?? 0

    for (const key in cache) {
      this.set(key, cache[key])
    }

    return this
  }

  /**
   * @param {number} indent
   * @returns {JSON} - string
   */
  toString (indent) {
    const replacer = (_, value) => {
      if (value instanceof Set) {
        return [...value]
      }

      if (value instanceof Map) {
        return Object.fromEntries(value)
      }

      return value
    }

    return JSON.stringify(this, replacer, indent)
  }
}

参考

• LRU & LFU 缓存机制的原理及实现 - 知乎 (opens new window)