LRU（最近最少使用）算法原理及PHP实现_由于内存是有限的

由于内存是有限的，因此缓存总有满的时候，那么当缓存满了的时候，这时候又有新的数据需要加入到缓存中时，我们该怎么办了？没什么别的办法，只有从缓存中删除旧数据为新数据腾出空间，那么究竟删除原来缓存的哪些数据了？这就涉及到缓存的替换策略，LRU就是一种缓存策略。

LRU，Least Recently Used的简写，翻译过来就是“最近最少使用”，其淘汰旧数据的策略是，距离当前最久没有被访问过的数据应该被淘汰。

LRU原理

假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，LRU就是这样工作的。

这样设计可能问题很多，内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。

那么如何设计一个LRU缓存，使得放入和移除都是 O(1) 的，我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用双向链表。

LRU（最近最少使用）算法原理及PHP实现