lru-缓存机制

题目

设计和实现一个 LRU (最近最少使用) 缓存机制:

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中, 则返回关键字的值, 否则返回 -1.

• void put(int key, int value) 如果关键字已经存在, 则变更其数据值; 如果关键字不存在, 则插入该组关键字-值. 当缓存容量达到上限时, 它应该在写入新数据之前删除最久未使用的数据值, 从而为新的数据值留出空间.

示例

const instance = new LRUCache(2)
instance.put(1, 1) // 缓存是 {1=1}
instance.put(2, 2) // 缓存是 {1=1, 2=2}
instance.get(1) // 返回 1
instance.put(3, 3) // 该操作会使得关键字 2 作废, 缓存是 {1=1, 3=3}
instance.get(2) // 返回 -1 (未找到)
instance.put(4, 4) // 该操作会使得关键字 1 作废, 缓存是 {4=4, 3=3}
instance.get(1) // 返回 -1 (未找到)
instance.get(3) // 返回 3
instance.get(4) // 返回 4

题解

这道题用 JavaScript 比较讨巧, 因为 Map 是有序的, 因此可以通过 this.caches.keys().next().value 拿到最老的 key. 像 Java 中有一个 LinkedHashMap, 它是 HashMap + LinkedList 的组合, 既使用 HashMap 操作数据结构, 又使用 LinkedList 维护插入元素的先后顺序.

info

该题的标准做法是维护一个双向链表和一个哈希表, 来代替 LinkedHashMap.

JavaScript

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

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  // 如果不存在, 返回 -1
  if (!this.caches.has(key)) return -1

  // 如果存在, 因为用过一次了, 就把它删除掉, 重新 set 一次
  const val = this.caches.get(key)
  this.caches.delete(key)
  this.caches.set(key, val)

  // 如果存在, 返回这个 val
  return val
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 如果存在, 先把它删除
  if (this.caches.has(key)) {
    this.caches.delete(key)
  }

  // 如果缓存大小恰好等于了容量, 就把 Map 最老的那个删除掉
  if (this.caches.size === this.capacity) {
    // 这里用到了迭代器的语法, 很优雅
    this.caches.delete(this.caches.keys().next().value)
  }

  // 新增 k-v
  this.caches.set(key, value)
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

JavaScript 双向链表

class ListNode {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.next = null
    this.prev = null
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity
    this.hash = {}
    this.count = 0
    this.dummyHead = new ListNode()
    this.dummyTail = new ListNode()
    this.dummyHead.next = this.dummyTail
    this.dummyTail.prev = this.dummyHead
  }

  get(key) {
    let node = this.hash[key]
    if (node == null) return -1
    this.moveToHead(node)
    return node.value
  }

  put(key, value) {
    let node = this.hash[key]
    if (node == null) {
      if (this.count == this.capacity) {
        this.removeLRUItem()
      }
      let newNode = new ListNode(key, value)
      this.hash[key] = newNode
      this.addToHead(newNode)
      this.count++
    } else {
      node.value = value
      this.moveToHead(node)
    }
  }

  moveToHead(node) {
    this.removeFromList(node)
    this.addToHead(node)
  }

  removeFromList(node) {
    let temp1 = node.prev
    let temp2 = node.next
    temp1.next = temp2
    temp2.prev = temp1
  }

  addToHead(node) {
    node.prev = this.dummyHead
    node.next = this.dummyHead.next
    this.dummyHead.next.prev = node
    this.dummyHead.next = node
  }

  removeLRUItem() {
    let tail = this.popTail()
    delete this.hash[tail.key]
    this.count--
  }

  popTail() {
    let tail = this.dummyTail.prev
    this.removeFromList(tail)
    return tail
  }
}

Rust

use linked_hash_map::LinkedHashMap;

#[derive(Debug)]
struct LRUCache {
    cache: LinkedHashMap<i32, i32>,
    capacity: i32,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl LRUCache {
    fn new(capacity: i32) -> Self {
        LRUCache {
            cache: LinkedHashMap::with_capacity(capacity as usize),
            capacity,
        }
    }

    fn get(&mut self, key: i32) -> i32 {
        if !self.cache.contains_key(&key) {
            -1
        } else {
            let value = *self.cache.get(&key).unwrap();
            self.cache.remove(&key);
            self.cache.insert(key, value);
            value
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        if self.cache.contains_key(&key) {
            self.cache.remove(&key);
        }

        if self.cache.len() == self.capacity as usize {
            let oldest_key = *self.cache.keys().next().unwrap();
            self.cache.remove(&oldest_key);
        }

        self.cache.insert(key, value);
    }
}

// /**
//  * Your LRUCache object will be instantiated and called as such:
//  * let obj = LRUCache::new(capacity);
//  * let ret_1: i32 = obj.get(key);
//  * obj.put(key, value);
//  */

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(n)