实现 LRU Cache 算法

双向链表+哈希表巧用 Map

// 用双向链表+哈希
/**
 * @param {number} capacity
 */
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)
  }
}

// 妙用 Map
// map 放入数据是按顺序的，最新放入的数据在迭代器最后 而且 map 的 entries 方法，
// 还有 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 (val !== undefined) {
    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.entries().next().value[0])
  }
}

实现 LRU Cache 算法 ​

实现 LRU Cache 算法