页面置换-LRU缓存淘汰算法

介绍

什么是LRU算法？ LRU是Least Recently Used的缩写，即最近最少使用，在有限的内容块中存储最近使用最多的数据，当内容块已满时，把最少使用的数据删除以便存储新的内容。

代码

在LRU算法当中，我们需要用到2种数据结构，一个是链表，一个是map。链表用来保存数据的前后顺序，每次有新数据加入时都插入到末尾，删除时则删除头结点；map用来快速查找数据。在这里，我们定义了一个模板类LruCache，K是map中的key值，V是map中的value值，K和V是一个键值对，知道K就可以快速查找到V。把K值存入到链表当中去，为什么不存V值呢？因为我们可以通过K值在map中查找V值，所以只需要在链表中存储K值就可以了，毕竟占用的内存越少越好。同时，我们在map中存储的value是V和链表的一个迭代器的pair数据，这是为了方便通过K值很快的就锁定其在链表当中的位置，而不需要去遍历查找链表。Functor是把K值转化成V值的一个hash算法。

LRU算法模板类的定义

LruCache类的构造函数接受2个参数，一个是Key和Value转换的hash算法函数，一个是可以保存的最大数据数量。

LRU算法的构造函数

LruCache类通过插入关键字Key查找Value值，如果Value值不存在的话，则会用传入的fun_算法生成一个Value值，插入到缓存中。如果存在的话，则先把当前访问到的数据在链表中把它放到最后，表明这个数据经常访问到，不要删除。

LRU算法通过Key找Value

插入的时候判断当前的缓存数量是否等于最大可以存储的数量，如果等于，则要删除最近最少使用的一个数据。如果小于，则在链表的最后插入这个数据，表明它是最近使用的多的数据，不要删除，同时插入到map当中。

LRU算法插入数据的过程

删除数据时，只需要删除链表最前面的数据就可以，因为最前面的数据表明它已经很久没有使用，所以可以删除。

LRU算法删除数据时删除最少使用的数据

提供一个输出函数，方便测试。

输出内容

测试代码，我们提供一个简单的算法，把传入的内容反逆序排列。然后我们定义一个最大缓存只有5的一个LRU缓存，当插入第6个数据时，因为数据已经满，所以它会删除最少使用的数据，即插入的第一个。如果我们把代码改成在插入第6个数据之前先访问一次第一个数据，那么插入时，删除的则会是第2个数据。

测试LRU算法，判断是否正确

总结

LRU算法对于经常需要访问的缓存数据的命中率很高，尤其是在页面置换当中是一种很有用的算法，但是如果数据访问很随机，造成经常会删除插入新的数据，可能就有些不尽如人意。需要了解更多的算法和编程问题，请关注我，谢谢。