LRU算法

LRU算法

简述

LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t 值最大的，即最近最少使用的页面予以淘汰。

需求

实现一个缓存功能，使得插入、删除、修改的操作都是O(1)的，并且当需要清除缓存时，需要从最少使用的开始清除。

实现

思考：

• 一般的，要实现O(1)的时间复杂度，考虑使用hash来实现
• 需要从最少的元素开始删起，一种朴素的想法就是将每个元素使用时间记录下来，按时间顺序排好序，然后需要删除时，从最久未使用的元素开始删除
• 进而可以想到，使用链表将哈希表串联起来，头部表示使用最近使用的，尾部表示最久未使用的

如图所示：

最左边为Head，表示最近使用的；最右边未Tail，表示最久未使用的

当对节点进行操作：

删除：将节点从链表中移除

增加：将节点移动到head处

修改：将节点移动到head处

查询：将节点移动到head处