Javascript中的LRU缓存实现

Question

Java有LinkedHashMap，其中gets you 99% there to an LRU cache。

是否有一个Javascript实现的LRU缓存的，最好是有信誉的来源，那就是：

1. 理解
2. 高效（摊销O（1）获得/ PUT /删除）

？我一直在网上搜索，但找不到一个;我以为我在Ajax Design Patterns上发现了一个，但它掩盖了sendToTail()方法并具有O（n）性能（可能是因为队列和关联数组已分离）。

我想我可以写我自己，但我学到了艰辛的方式，重塑核心算法的车轮会危害人的健康：/

Answer 1

此：

https://github.com/monsur/jscache

似乎适合你的情况，尽管setItem（即put）在最坏的情况下是O（N），如果缓存在插入时被填满，就会发生这种情况。在这种情况下，搜索缓存以清除过期项目或最近最少使用的项目。 getItem为O（1），并在getItem操作上处理到期（即，如果正在提取的项目已过期，则将其删除并返回空值）。

代码非常简洁，易于理解。

P.S.向构造函数添加指定fillFactor的选项可能会很有用，该选项固定为0.75（意思是当清除缓存时，它的大小至少减小到最大大小的3/4）

Answer 2

这不是一个LRU缓存，但我有my own linked map implementation。由于它使用JS对象作为存储，它将具有相似的性能特征（包装对象和散列函数会带来性能损失）。

目前，文档是basically non-existant，但有一个related SO answer。

的each()方法将通过当前键，当前值和表示如果有更多的元素作为参数给回调函数布尔值。

另外，循环可以通过手动

for(var i = map.size; i--; map.next()) { 
    var currentKey = map.key(); 
    var currentValue = map.value(); 
} 

Answer 3

所做的monsur.com实现在插入为O（n），不仅是因为它具有实际真实世界时间到期的项目。这不是一个简单的LRU。如果您只关心维护最近使用的项目而不考虑现实世界时间，则可以在O（1）中完成。实现为双向链接列表的队列是O（1），用于从最后插入或删除，这就是缓存所需的全部内容。至于查找，一个哈希映射，这使JavaScript可以很容易，几乎O（1）查找应该是好的（假设JavaScript引擎使用一个很好的哈希映射，当然这取决于实现）。所以你有一个项目的链表和一个指向项目的哈希映射。根据需要操作链表的末端，以便将新项目和请求的项目放在一端，并从另一端删除旧项目。

Answer 4

我知道这是一个老问题，但为未来的参考添加一个链接。 结账https://github.com/monmohan/dsjslib。除了一些其他数据结构之外，它还有一个LRU Cache实现。这样的高速缓存（并且也是这个高速缓存）以LRU顺序维护双向链接的高速缓存条目列表，即当它们被访问时条目移动到头部，并且当它们被回收（例如到期或者因为达到大小限制）时从尾部移除。它的O（1），因为它只涉及数量不变的指针操作。

Answer 5

这是值得一提： https://github.com/rsms/js-lru

这套核心的功能是O（1）和代码是大量注释

Answer 6

这并不像你那样有效（用ASCII艺术呢！）想要，但它在简单性和可读性方面弥补了这一点。而且在很多情况下，它会很快。

我需要一个简单的LRU缓存来处理少量昂贵的操作（1秒）。我觉得有关的复制粘贴一些小的代码，而不是引入外在的东西更好，但因为我没有找到我写的：

更新：这是现在很多更有效的（时间和空间），因为我删除了数组，因为Map保持了插入顺序。

class LRU { 
    constructor(max=10) { 
     this.max = max; 
     this.cache = new Map(); 
    } 
    get(key) { 
     let item = this.cache.get(key); 
     if (item) // refresh key 
     { 
      this.cache.delete(key); 
      this.cache.set(key, item); 
     } 
     return item; 
    } 
    set(key, val) { 
     if (this.cache.has(key)) // refresh key 
      this.cache.delete(key); 
     else if (this.cache.size == this.max) // evict oldest 
      this.cache.delete(this._first()); 
     this.cache.set(key, val); 
    } 
    _first(){ 
     return this.cache.keys().next().value; 
    } 
} 

用法：

> let cache = new LRU(3) 
> [1, 2, 3, 4, 5].forEach(v => cache.set(v, 'v:'+v)) 
> cache.get(2) 
undefined 
> cache.get(3) 
"v:3" 
> cache.set(6, 6) 
> cache.get(4) 
undefined 
> cache.get(3) 
"v:3"