##概念分析
LRU(Least Recent Used):最近最少使用，就是将最近最少使用的页淘汰掉，替换为新的页。核心思想是：如果一个页最近被访问了，那他之后被访问的概率也高；如果一个页最近没有被访问，那他之后也不会被访问。这道理其实说不通哈，但是LRU算法确实解决页访问的效率问题。
##原理
下面是一个应用LRU算法的例子的流程图
下面简单讲解一下(需要在这里说明一下,LRU一般采用链表方式实现,便于快速移动数据位置,虽然图中使用似乎是数组方式):
- 一开始,缓存池是空的,缓存池中插入数据时不用担心容量不足的事情.因此这个过程就是类似队列的FIFO(但不止这些);
- 在第5步将E插入到缓存池中后,缓存池已经满了(当然实际应用中不会让到达缓存池的尺寸,一般到70%左右就要考虑淘汰机制了);
- 当第6步将E插入缓存池的时候,发现缓存池已经满了,LRU会将最早加入到缓存池的数据淘汰掉(A,实在不要意思啊);
- 第7步,从缓存池中访问C,C被访问,从时间点上是最近最近访问的,将C移动到链表的头部(C侥幸暂时远离被淘汰的边缘);
- 第8步,将G插入缓存池中,G处于链表头部,B不幸被淘汰.
大致的过程就是这样,关于淘汰机制只是后面的三步中会用到,画出前面六步的过程只是说明LRU插入元素的方式.在这个图中,我想大家应该可以明白为什么使用链表,而不使用数组(链表的插入和删除的时间复杂度都是O(1)).
##优劣分析
###命中率
命中率较高,不过偶发性的情况对LRU的命中影响很大,同时也会引入很多数据污染
###复杂度
实现起来较为简单.
###存储成本
几乎没有空间上浪费.
###缺陷
仅仅从最近使用时间上考虑淘汰算法,没有考虑缓存单元的使用频率,可能会淘汰一些仍有价值的单元.