LRU算法

722

LRU算法

简述

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

需求

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

实现

思考:

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

image-20210527220814816

如图所示:

最左边为Head,表示最近使用的;最右边未Tail,表示最久未使用的

当对节点进行操作:

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

增加:将节点移动到head处

修改:将节点移动到head处

查询:将节点移动到head处