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的方法很多,比如用双向队列+哈希等。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20200302A0SI5000?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券