LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。

现代操作系统提供了一种对主存的抽象概念虚拟内存，来对主存进行更好地管理。他将主存看成是一个存储在磁盘上的地址空间的高速缓存，在主存中只保存活动区域，并根据需要在主存和磁盘之间来回传送数据。虚拟内存被组织为存放在磁盘上的N个连续的字节组成的数组，每个字节都有唯一的虚拟地址，作为到数组的索引。虚拟内存被分割为大小固定的数据块虚拟页(Virtual Page,VP)，这些数据块作为主存和磁盘之间的传输单元。类似地，物理内存被分割为物理页(Physical Page,PP)。

虚拟内存使用页表来记录和判断一个虚拟页是否缓存在物理内存中：

如上图所示，当CPU访问虚拟页VP3时，发现VP3并未缓存在物理内存之中，这称之为缺页，现在需要将VP3从磁盘复制到物理内存中，但在此之前，为了保持原有空间的大小，需要在物理内存中选择一个牺牲页，将其复制到磁盘中，这称之为交换或者页面调度，图中的牺牲页为VP4。把哪个页面调出去可以达到调动尽量少的目的？最好是每次调换出的页面是所有内存页面中最迟将被使用的——这可以最大限度的推迟页面调换，这种算法，被称为理想页面置换算法，但这种算法很难完美达到。

为了尽量减少与理想算法的差距，产生了各种精妙的算法，LRU算法便是其中一个。

根据LRU原理和Redis实现所示，假定系统为某进程分配了3个物理块，进程运行时的页面走向为 7 0 1 2 0 3 0 4，开始时3个物理块均为空，那么LRU算法是如下工作的：

如果要自己实现一个LRU算法，可以用哈希表加双向链表实现：

设计思路是，使用哈希表存储 key，值为链表中的节点，节点中存储值，双向链表来记录节点的顺序，头部为最近访问节点。

LRU算法中有两种基本操作：

leetcode上有一道关于LRU缓存机制的题目：

OrderedDict有两个重要方法：

删除数据时，可以使用popitem(last=False)将开头最近未访问的键值对删除。访问或者设置数据时，使用move_to_end(key, last=True)将键值对移动至末尾。

代码实现：

 OrderedDict其实也是用哈希表与双向链表实现的：

　由源码看出，OrderedDict使用self.__map = {}作为哈希表，其中保存了key与链表中的节点Link()的键值对，self.__map[key] = link = Link():

  节点Link()中保存了指向前一个节点的指针prev，指向后一个节点的指针next以及key值。

  而且，这里的链表是一个环形双向链表,OrderedDict使用一个哨兵元素root作为链表的head与tail：

  由__setitem__可知，向OrderedDict中添加新值时，链表变为如下的环形结构：

 root.next为链表的第一个节点，root.prev为链表的最后一个节点。

  由于OrderedDict继承自dict，键值对是保存在OrderedDict自身中的，链表节点中只保存了key，并未保存value。

  如果我们要自己实现的话，无需如此复杂，可以将value置于节点之中，链表只需要实现插入最前端与移除最后端节点的功能即可：

在实际应用中，要实现LRU缓存算法，还要实现很多额外的功能。

这个包不是用缓存key的数量来判断是否要启动LRU淘汰算法，而是使用保存的键值对的实际大小来判断。选项options中可以设置缓存所占空间的上限max，判断键值对所占空间的函数length，还可以设置键值对的过期时间maxAge等，有兴趣的可以看下。