LRU 缓存题库

一、认识

LRU 缓存(Least Recently Used) 最近最少使用的缓存,是一种缓存淘汰策略, 根据数据的历史访问记录来进行淘汰数据。 它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素。整个流程大致为:

新加入的数据插入到第一项
每当缓存命中（即缓存数据被访问），则将数据提升到第一项
当缓存数量满的时候，将最后一项的数据丢弃

二、实现

2.1 JS Map

Map 的遍历顺序严格按照插入顺序输出, 因此, 我们可以将新加入的缓存通过 map.set 放置到后面, 缓存越靠后说明缓存越活跃。如果超出 capacity 容器容量, 删除最前面插入的缓存 map.keys().next().value。

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

  get(key) {
    if (this.cache.has(key)) {
      const temp = this.cache.get(key);
      this.cache.delete(key);
      this.cache.set(key, temp);
      return temp;
    }
    return null;
  }

  set(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      this.cache.delete(this.cache.keys().next().value);
    }
    this.cache.set(key, value);
  }
}

测试代码

[[1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]].forEach((item) => {
  if (item.length == 1) {
    eval(`console.log(lru.get(${item[0]}))`);
  } else {
    eval(`lru.set(${item[0]},${item[1]})`);
  }
});

2.2 JS Array

设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现LRUCache类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ; 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity , 则应该逐出最久未使用的关键字

函数get和put必须以 O(1) 的平均时间复杂度运行。

思路

LRU 缓存机制可以通过对象辅助一个数组来实现。对象用于存储缓存数据; 数组用于记录缓存访问的顺序，最近访问的位于数组头部，最久未使用的位于数组尾部。

class LRUCache {
  constructor(max) {
    this.max = max;
    this.keys = [];
    this.size = 0;
    this.cache = Object.create(null);
  }
  remove(key) {
    const { length } = this.keys;
    if (length) {
      if (key === this.keys[length - 1]) {
        this.keys.length = length - 1;
        return;
      }
      const index = this.keys.indexOf(key);
      if (index !== -1) {
        return this.keys.splice(index, 1);
      }
    }
  }
  moveToHead(key) {
    this.remove(key);
    this.keys.unshift(key);
  }
  get(key) {
    const cache = this.cache[key];
    if (!cache) {
      return null;
    }
    this.moveToHead(key);
    return cache;
  }
  put(key, value) {
    const cache = this.cache[key];
    if (!cache) {
      const newCache = {
        key,
        value,
      };
      this.cache[key] = newCache;
      this.moveToHead(key);
      this.size++;
      if (this.size > this.max) {
        const tailKey = this.keys.pop();
        this.cache[tailKey] = null;
        this.size--;
      }
    } else {
      cache.value = value;
      this.moveToHead(key);
    }
  }
}

测试代码

const lru = new LRUCache(2);

[[1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]].forEach((item) => {
  if (item.length == 1) {
    eval(`console.log(lru.get(${item[0]}))`);
  } else {
    eval(`lru.put(${item[0]},${item[1]})`);
  }
});

2.3 Java HashMap

设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。实现LRUCache类:

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ; 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity , 则应该逐出最久未使用的关键字

函数get和put必须以 O(1) 的平均时间复杂度运行。

思路

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。

双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置

这样一来，我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部,即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下:

对于 get 操作，首先判断 key 是否存在:
- 如果 key 不存在，则返回 -1
- 如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值
对于 put 操作，首先判断 key 是否存在:
- 如果 key 不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项
- 如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部

实现

class HashMap {
  constructor(capacity) {
    this.size = 0;
    this.capacity = capacity || 769;
    this.data = new Array(this.capacity).fill(0).map(() => new Array());
  }
  hash(key) {
    return key % this.capacity;
  }
  put(key, value) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        item[1] = value;
        return;
      }
    }
    this.size++;
    this.data[hash].push([key, value]);
  }
  get(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return item[1];
      }
    }
    return null;
  }
  remove(key) {
    const hash = this.hash(key);
    const index = this.data[hash].findIndex((item) => item[0] === key);
    if (index !== -1) {
      this.size--;
      this.data[hash].splice(index, 1);
      return true;
    }
    return false;
  }
}
class Node {
  next;
  prev;
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}
class LRUCache {
  constructor(capacity) {
    this.size = 0;
    this.capacity = capacity;
    this.hashMap = new HashMap();
    this.dummyHead = new Node();
    this.dummyTail = new Node();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }
  addToHead(node) {
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = node;
  }
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }
  removeTail() {
    const result = this.dummyTail.prev;
    this.removeNode(result);
    return result;
  }
  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }
  get(key) {
    const node = this.hashMap.get(key);
    if (node == null) {
      return -1;
    }
    this.moveToHead(node);
    return node.value;
  }
  put(key, value) {
    const node = this.hashMap.get(key);
    if (node == null) {
      const newNode = new Node(key, value);
      this.hashMap.put(key, newNode);
      this.addToHead(newNode);
      this.size++;
      if (this.size > this.capacity) {
        const tail = this.removeTail();
        this.hashMap.remove(tail.key);
        this.size--;
      }
    } else {
      node.value = value;
      this.moveToHead(node);
    }
  }
}

测试

const lru = new LRUCache(2);

[[1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]].forEach((item) => {
  if (item.length == 1) {
    eval(`console.log(lru.get(${item[0]}))`);
  } else {
    eval(`lru.put(${item[0]},${item[1]})`);
  }
});

一、认识​

二、实现​

2.1 JS Map​

2.2 JS Array​

2.3 Java HashMap​

一、认识

二、实现

2.1 JS Map

2.2 JS Array

2.3 Java HashMap