BFE.devAI解答 - JavaScript 代码题
169. LRU - Chrome storage自动清除算法

以下是实现的JavaScript代码：

class LRUStorage {
  constructor(capacity, getTimestamp = Date.now) {
    this.capacity = capacity;
    this.getTimestamp = getTimestamp;
    this.data = new Map();
    this.head = null;
    this.tail = null;
    this.size = 0;
    this.persistentSize = 0;
  }

  getData(origin) {
    const node = this.data.get(origin);
    if (node) {
      node.lastUsed = this.getTimestamp();
      this.moveToHead(node);
      return {
        origin: node.origin,
        lastUsed: node.lastUsed,
        size: node.size,
        persistent: node.persistent,
      };
    }
  }

  setData(origin, size) {
    let node = this.data.get(origin);
    if (!node) {
      node = {
        origin,
        lastUsed: this.getTimestamp(),
        size,
        persistent: false,
        prev: null,
        next: null,
      };
      this.data.set(origin, node);
      this.addToHead(node);
    } else {
      node.lastUsed = this.getTimestamp();
      node.size = size;
      this.moveToHead(node);
    }
    if (!node.persistent) {
      while (this.size + size > this.capacity) {
        this.removeTail();
      }
      this.size += size - node.size;
      node.size = size;
      return true;
    }
    return false;
  }

  clearData(origin) {
    const node = this.data.get(origin);
    if (node) {
      this.removeNode(node);
      this.data.delete(origin);
      this.size -= node.size;
      this.persistentSize -= node.persistent ? node.size : 0;
    }
  }

  makePersistent(origin) {
    const node = this.data.get(origin);
    if (node && !node.persistent) {
      this.removeNode(node);
      this.persistentSize += node.size;
      node.persistent = true;
      this.addToHead(node);
      while (this.size + this.persistentSize > this.capacity) {
        this.removeTail();
      }
    }
  }

  addToHead(node) {
    if (!this.head) {
      this.head = this.tail = node;
    } else {
      node.next = this.head;
      this.head.prev = node;
      this.head = node;
    }
  }

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

  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }

  removeTail() {
    if (this.tail) {
      this.data.delete(this.tail.origin);
      this.size -= this.tail.size;
      this.persistentSize -= this.tail.persistent ? this.tail.size : 0;
      this.removeNode(this.tail);
    }
  }
}

该类实现了一个最近最少使用（LRU）缓存算法，可以在容量限制内存储和访问数据，并且在超出容量限制时自动清除最近最少使用的非持久化数据。

在实现中，使用了双向链表来维护访问顺序，并使用 Map 来快速索引数据。每个节点包含了 OriginData 的信息，以及双向链表中的前驱和后继节点。addToHead 方法用于添加节点到链表头，removeNode 方法用于移除节点，moveToHead 方法将节点移动到链表头。另外，removeTail 方法用于移除链表末尾的节点，相当于删除最近最少使用的数据。setData 方法中，首先判断数据是否已存在于缓存中，如果已存在则更新数据，否则添加新数据。如果新添加的数据不是持久化数据，则不断尝试移除末尾的节点，直到缓存的总大小小于等于容量限制。

在 makePersistent 方法中，将指定数据标记为持久化数据，并将数据移动到链表头部，如果此时缓存的总大小超过了容量限制，则尝试移除末尾的非持久化数据节点。在 clearData 方法中，移除给定数据的节点，并从 Map 中删除。在 getData 方法中，获取指定数据的节点并将其移动到链表头部，并返回节点的 OriginData 信息。

需要注意，默认使用的是 Date.now 函数来获取当前时间，也可以通过参数 getTimestamp 指定时间戳的获取方法。在实际使用中，可以通过装饰模式等方法将 LRUStorage 封装为一个全局单例，提供缓存数据的统一管理。