LRU Cache的实现

LRU Cache的实现

LRU（Least Recently Used）即最近最少使用，这算法应用于一些操作系统和应用程序中。

咱们就看看LRU Cache的实现，实现这个算法一般需要两部分，一个类似字典的数据结构能快速找到数据，一个保存有序数据的链表。

一种实现方式可以把所有的数据放到一个集合里面，集合定义一个大小，每个数据拥有一个访问时间戳，插入和更新的时候，也更新这个时间戳，队列满时候删除时间最老的就行。

另一种实现方式可以用双向链表，每次插入或者更新都放在head，删除在tail，简单实现这种功能。

其实用JDK提供的集合类可以很简单的实现这种功能，那就是LinkedHashMap。

LRU Cache实现

做个简单测试，设置cache容量是3，先放入三个数据，等再添加第四个的时候，会把最近最少使用的一个删除。

一个简单测试

输出结果如下，发现zhang不存在了，

-----------------缓存刚满---------------

-----------------缓存已满，最老的已经删除---------------

稍微改下程序，在添加zhao的时候，先获取下zhang，又是另一种结果。现在zhang是存在的，wang没有了。

另一个测试

-----------------缓存刚满---------------

-----------------缓存已满，最老的已经删除---------------

下面就看看LinkedHashMap实现LRU的原理。

1、我们在构造LinkedHashMap的时候，传入容量和访问的顺序accessOrder。这个accessOrder有两个值，false的时候是插入的顺序，true的时候是访问的顺序。

LinkedHashMap

2、removeEldestEntry方法，该方法控制在容量满的时候的行为，返回true，表示要删除最老的entry，返回false，就像普通的map一样会扩容。这个方法会在put和putAll方法中调用。

3、get方法，如果是accessOrder为true,会把当前Node移到最后。

其实实现LRU的方法很多，比如用双向队列+哈希等。