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 封装为一个全局单例，提供缓存数据的统一管理。