前端开发者必知的缓存淘汰策略：LRU算法解析与实践

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

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cacheMap = new Map(); // 使用哈希表
    this.head = new LRUCacheNode(null, null); // 双向链表头节点
    this.tail = new LRUCacheNode(null, null); // 双向链表尾节点
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  // 其他LRU缓存方法（如get、put等）
}

class LRUCache {
  constructor(capacity = 500) {
    this.capacity = capacity;
    this.cacheMap = new Map(); // 使用哈希表存储键值对
    this.doubleLinkedList = new DoublyLinkedList(); // 双向链表维护缓存顺序
  }

  get(key) {
    if (this.cacheMap.has(key)) {
      const node = this.cacheMap.get(key);
      this.doubleLinkedList.moveToTail(node); // 将节点移动到链表尾部，表示最新访问
      return node.value;
    }
    return -1; // 或者返回null，表示key不存在于缓存中
  }

  put(key, value) {
    if (this.cacheMap.has(key)) {
      const node = this.cacheMap.get(key);
      node.value = value;
      this.doubleLinkedList.moveToTail(node);
    } else {
      if (this.cacheMap.size >= this.capacity) {
        const headNode = this.doubleLinkedList.deleteHead();
        this.cacheMap.delete(headNode.key); // 移除最旧的缓存项
      }
      const newNode = new Node(key, value);
      this.cacheMap.set(key, newNode);
      this.doubleLinkedList.addToTail(newNode);
    }
  }
}

// 双向链表类和节点类的实现略（根据实际需求实现）
class Node {
  constructor(key, value) {
    this.key = key; // 节点键值
    this.value = value; // 节点数据值
    this.prev = null; // 前驱节点引用
    this.next = null; // 后继节点引用
  }
}
class DoublyLinkedList {
  constructor() {
    this.head = null; // 头节点
    this.tail = null; // 尾节点
  }

  /**
   * 添加节点到链表尾部
   * @param {Node} newNode 新节点
   */
  addToTail(newNode) {
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  /**
   * 移除头节点并返回
   * @returns {Node | null} 删除的头节点或null（如果链表为空）
   */
  deleteHead() {
    if (!this.head) return null;

    const deletedNode = this.head;
    this.head = this.head.next;

    if (this.head) {
      this.head.prev = null;
    } else {
      this.tail = null;
    }

    return deletedNode;
  }

  /**
   * 将指定节点移动到链表尾部
   * @param {Node} node 需要移动的节点
   */
  moveToTail(node) {
    if (node === this.tail) return; // 如果已经是尾节点，则无需移动

    // 断开当前节点与前后节点的连接
    node.prev.next = node.next;
    if (node.next) node.next.prev = node.prev;

    // 将节点添加至链表尾部
    this.addToTail(node);
  }
  
  // 其他可能的方法，如查找节点、在指定位置插入节点等...
}

class LRUWishGenerator {
  constructor(capacity = 5) {
    this.wishesCache = new LRUCache(capacity);
  }

  generateWishFor(name) {
    const cachedWish = this.wishesCache.get(name);
    if (cachedWish) {
      console.log(`Cached wish for ${name}:`, cachedWish);
      return cachedWish;
    } else {
      const freshWish = `May the code always compile and your bugs be few, dear ${name}!`;
      this.wishesCache.put(name, freshWish);
      console.log(`Fresh wish generated for ${name}:`, freshWish);
      return freshWish;
    }
  }
}

const generator = new LRUWishGenerator(3);

generator.generateWishFor('Alice');
generator.generateWishFor('Bob');
generator.generateWishFor('Charlie');
generator.generateWishFor('Alice'); // 这次 Alice 的祝福语会被从缓存中取出
generator.generateWishFor('David');
generator.generateWishFor('Eve'); // 此时缓存已满，最早生成的 Bob 的祝福语会被淘汰

/* 输出示例：
Fresh wish generated for Alice: May the code always compile and your bugs be few, dear Alice!
Fresh wish generated for Bob: ...
Fresh wish generated for Charlie: ...
Cached wish for Alice: May the code always compile and your bugs be few, dear Alice!
Fresh wish generated for David: ...
Fresh wish generated for Eve: ... (此时Bob的祝福语已经被淘汰)
*/