LRU缓存置换算法

这篇文章是科普性质的，外加推销一下中文注释……

LRU(Least Recently Used, 近期最少使用)算法是缓存置换算法当中的经典案例——这个中文翻译听起来相当莫名其妙，所以我们还是叫LRU吧。虽然我们现在常常都用了更高阶的缓存服务，但如果要在一些语言（比如JS）当中自己实现一个简单的K-V的缓存类的时候，不放试试写一个LRU，因为它的算法思路真的相当简单，但实现起来又是非常有趣。

为什么需要置换算法

实现一个K-V cache的类，我们需要什么API？精简下来，我认为说到底就3个吧：

1
2
3
get(key)
set(key, value)
del(key)

这看起来就是一个字典而已，和LRU没什么关系。问题就在于缓存的空间是有限的，要么是硬件受限，要么是我们不想给这么多内存。所以当空间满的时候，再添加新的缓存，需要置换出去旧的。置换哪个出去就是门学问了。

最容易的比如FIFO，先进先出，其他还有很多，这里不详细介绍了，可以去翻翻计算机组成原理看看。

LRU置换算法介绍

其实思路很简单，就是“把最近没用过的一个置换出去”。
实现上，可以描述为一个双端的列表，表头是最近用过的，而表尾是最近没用过的。

1
2
3
4
set时，如果缓存在列表里，把它摘出来放在表头上，否则直接放在表头上。
get时，把它摘出来放在表头上。
del时，把它摘出来释放掉，如果它是表尾，那么维护一下新的表尾。
置换时，换出表尾释放掉。

很明显用一个双端队列可以比较容易地实现上述算法，主要的问题是：用双链表构造的双端队列，因为不能随机访问，在按key查找时，需要O(n)的时间查找。（根据局部性原理，从队头查找会更容易快速找到目标，这是一个优化点。）

JS实现

isaacs大神（npm以及node.js的主要作者）的node-lru-cache里用的是hash表加上队头和队尾两个索引来替代双链表。这样可以获得分摊O(1)时间的查找，构造比较巧妙。

我把它的源代码加了中文注释，还算比较详细吧，有兴趣的童鞋可以去看看。github