LFU
LFU(Least Frequently Used ,最近最少使用算法)
算法描述:
1 | class LFUCache { |
get(key)
方法会去缓存中查询键key
,如果key
存在,则返回key
对应的val
,否则返回 -1。
put(key, value)
方法插入或修改缓存。如果key
已存在,则将它对应的值改为val
;如果key
不存在,则插入键值对(key, val)
。
当缓存达到容量capacity
时,则应该在插入新的键值对之前,删除使用频次(后文用freq
表示)最低的键值对。如果freq
最低的键值对有多个,则删除其中最旧的那个。
思路:
- 需要有一个HashMap来保存key到val的映射,用来计算
get(key)
1 | HashMap<Integer, Integer> keyToVal; |
- 需要有一个HashMap来保存
key
到freq
的映射,用来计算每一个key的频次
1 | HashMap<Integer, Integer> keyToFreq; |
算法的核心需求(思路)
- 需要
freq
到key
的映射,用来找到最小freq
对应的key
- 如果要满足上一条,快速找到最小
freq
是多少,可以通过一个变量minFreq
来记录当前最小freq
,避免遍历 - 可能会有多个
key
拥有相同的freq
,所以freq
和key
是一对多的关系,那么就需要维护一个freq
到key对应的映射关系 - 为了保证快速查找并删除最旧的
key
,就需要保证freq
对应的key
的映射列表应该是有顺序的 - 需要能够快速删除
key
列表中的任何一个key。如果频次为freq
的key
被访问了,它的频次应该变成freq+1
,此时应该从freq对应的key
列表中删除,并把key
加入到freq+1
对应的key列表中 => 就是需要提高它的频次
1
2HashMap<Integer, LinkedHashSet<Integer>> freqToKeys;
int minFreq;- 需要
如果用 LinkedList 可以满足第3、4条,但是链表不能快速访问某一个节点,所以不能满足第5条快速删除
综上,LFUCache
类代码如下:
1 | class LFUCache { |