实现 LRU Cache 算法

缓存淘汰算法

LRU 的全称是 Least Recently Used，最近使用原则

双向链表 + 哈希表对象 key 的排序特性巧用 Map

/**
 * @param {number} capacity
 * 用双向链表 + 哈希
 * 这里需要实现双向链表，还用到 map，实际仅用 map 即可支持
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
  this.cache = new DoubleList()
}
class Node {
  constructor(k, val) {
    this.k = k
    this.val = val
    this.pre = null
    this.next = null
  }
}
class DoubleList {
  constructor() {
    this.size = 0
    this.head = new Node(0, 0)
    this.tail = new Node(0, 0)
    this.head.next = this.tail
    this.tail.pre = this.head
  }
  addLast(x) {
    const { head, tail } = this
    x.pre = tail.pre
    x.next = tail
    tail.pre.next = x
    tail.pre = x
    this.size++
  }
  remove(x) {
    x.pre.next = x.next
    x.next.pre = x.pre
    this.size--
  }
  removeFirst() {
    const { head, tail } = this
    if (head.next === tail) return null
    let first = head.next
    this.remove(first)
    return first
  }
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  const { cache, map } = this
  if (map.has(key)) {
    let x = map.get(key)
    cache.remove(x)
    cache.addLast(x)
    return map.get(key).val
  } else {
    return -1
  }
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const { cache, map, size } = this
  const addRecently = function (key, value) {
    let x = new Node(key, value)
    cache.addLast(x)
    map.set(key, x)
  }
  if (map.has(key)) {
    let x = map.get(key)
    cache.remove(x)
    map.delete(key)
    addRecently(key, value)
  } else {
    if (cache.size === this.capacity) {
      let x = cache.removeFirst()
      map.delete(x.k)
    }
    addRecently(key, value)
  }
}

/**
 * @param {number} capacity
 */
// 利用对象 key 的排序特性（也可以换成数组实现）
const LRUCache = function (capacity) {
  this._cache = {}
  this._len = 0
  this._maxLen = capacity
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  key = 'c' + key
  const cur = this._cache[key]
  if (typeof cur !== 'undefined') {
    // 使用则更新使用的排序
    delete this._cache[key]
    this._cache[key] = cur
    return cur
  }
  return -1
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  key = 'c' + key
  const len = this._len
  const maxLen = this._maxLen

  const cur = this._cache[key]
  if (typeof cur !== 'undefined') {
    delete this._cache[key]
    this._cache[key] = value
  } else {
    if (len < maxLen) {
      this._cache[key] = value
      this._len = len + 1
    } else if (len >= maxLen) {
      const dropKey = Object.keys(this._cache).shift()
      delete this._cache[dropKey]
      this._cache[key] = value
    }
  }
}

// 妙用 Map【推荐】
// map 放入数据是按顺序的，最新放入的数据在迭代器最后
// map 的 keys 方法，会返回一个迭代器，迭代器调用 next 也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可

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

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  const map = this.map
  let val = map.get(key)
  if (![null, undefined].includes(val)) {
    map.delete(key)
    map.set(key, val)
    return val
  } else {
    return -1
  }
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const { map, capacity } = this
  if (map.has(key)) map.delete(key)
  map.set(key, value)
  if (map.size > capacity) {
    map.delete(map.keys().next().value)
  }
}

// 此处利用 Iterator 遍历器特性 获取第一项值
// 也可使用 map.entries().next().value[0]

实现 LRU Cache 算法 ​

实现 LRU Cache 算法