笔记大全

JavaScript怎么实现LRU缓存淘汰算法

更新时间：2023-10-21

LRU（Least Recently Used）缓存淘汰算法是一种常用的缓存淘汰策略，其基本思想是淘汰最近最久未使用的数据，保留最近使用的数据。在实际应用中，经常使用LRU算法来管理内存中的缓存，提高数据访问效率。本文将介绍如何使用JavaScript实现LRU缓存淘汰算法。首先，我们需要定义一个数据结构来实现LRU缓存算法。双向链表是一个较好的选择，因为它能够在常量时间内实现节点的插入和删除操作。同时，我们还需要使用一个哈希表来存储每个节点的引用，以便能够快速找到对应的节点。 ```html

1. 定义双向链表节点

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

上述代码定义了一个节点类ListNode，它具有key和value属性，以及前一个节点prev和后一个节点next的引用。接下来，我们实现一个LRUCache类，该类封装了LRU缓存算法的具体实现。 ```html

2. 实现LRU缓存类

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;         // 缓存容量
    this.size = 0;                    // 当前缓存大小
    this.head = new ListNode(null, null);   // 头节点
    this.tail = new ListNode(null, null);   // 尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.map = new Map();             // 哈希表存储节点
  }
}

上述代码中，我们定义了一个LRUCache类，其构造函数接受一个capacity参数，表示缓存的容量。LRUCache类具有size、head、tail和map等属性。head和tail分别表示双向链表的头尾节点，size表示当前缓存的大小，map用于存储节点的引用。接下来，我们实现LRUCache类的主要方法。 ```html

3. 实现LRU缓存算法

class LRUCache {
  // ...
  
  put(key, value) {
    let node = this.map.get(key);
    if (node) {
      // 更新节点值，并将节点移到链表头部
      node.value = value;
      this.moveToHead(node);
    } else {
      // 添加新节点，如果超出容量，则淘汰最久未使用的节点
      if (this.size >= this.capacity) {
        this.removeLRUItem();
      }
      let newNode = new ListNode(key, value);
      this.map.set(key, newNode);
      this.addToHead(newNode);
      this.size++;
    }
  }
  
  get(key) {
    let node = this.map.get(key);
    if (node) {
      // 将访问的节点移到链表头部
      this.moveToHead(node);
      return node.value;
    } else {
      return -1;   // 未找到对应的节点
    }
  }
  
  // 将节点移到链表头部
  moveToHead(node) {
    this.removeFromList(node);
    this.addToHead(node);
  }
  
  // 在链表头部添加节点
  addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }
  
  // 从链表中删除节点
  removeFromList(node) {
    let prevNode = node.prev;
    let nextNode = node.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }
  
  // 淘汰最久未使用的节点
  removeLRUItem() {
    let tailNode = this.tail.prev;
    this.removeFromList(tailNode);
    this.map.delete(tailNode.key);
    this.size--;
  }
}

上述代码中，put方法用于添加缓存数据，如果已存在对应的key，则更新其value，并将节点移到链表头部；如果不存在对应的key，则创建新节点，并将其添加到链表头部，同时判断缓存大小是否超出容量，若超出，则淘汰最久未使用的节点。get方法用于获取缓存数据，若存在对应的key，则返回其value，并将节点移到链表头部；否则，返回-1。moveToHead方法用于将节点移到链表头部，addToHead方法用于在链表头部添加节点，removeFromList方法用于从链表中删除节点，removeLRUItem方法用于淘汰最久未使用的节点。最后，我们可以将LRUCache类实例化，然后使用put和get方法来操作缓存。 ```html

4. 实例化和使用LRUCache

let cache = new LRUCache(2);    // 缓存容量为2

cache.put(1, "apple");
cache.put(2, "banana");
console.log(cache.get(1));     // 输出: "apple"
cache.put(3, "orange");         // 缓存容量已满，淘汰key=2的节点
console.log(cache.get(2));     // 输出: -1（未找到对应的节点）
console.log(cache.get(3));     // 输出: "orange"

上述代码中，我们首先实例化了一个容量为2的LRUCache对象，然后使用put方法向缓存中添加数据，使用get方法获取数据。当缓存容量已满时，put方法将会淘汰最久未使用的节点。通过以上步骤，我们成功地使用JavaScript实现了LRU缓存淘汰算法。该算法能够保证最近使用的数据始终位于缓存中，提高了数据访问效率。在实际应用中，我们可以根据实际需求调整缓存容量大小，以满足不同场景下的需求。

c语言编程笔录