LRU Cache
时间：2019-08-12 18:19:34
收藏：0
阅读：120
Cache 缓存
1. 记忆
2. 空间有限
3. 钱包 - 储物柜
4. 类似背代码模板，O(n) 变 O(1)
LRU Cache
缓存替换算法
1. Least Recently Used（最近最少使?的淘汰掉）
2. Hash Table + Double LinkedList（哈希表 + 双向链表）
3. O(1) 查询 （cache只要查询第一个）
4. O(1) 修改、更新（同3；要是处理最中间的话就是O(n)了）
双向链表实现：
LFU Cache
也记录元素出现的频次，即使最近刚出现的，也未必就会挪到最前面。
缓存内始终按频次排序，如果超了缓存空间限制，还是新进的元素把原先频次最低的顶走。
1. LFU - least frequently used（最近最不常用??置换算法，频次越高的放越前面)
2. LRU - least recently usd（最近最少使?页?置换算法)
原文：https://www.cnblogs.com/chaojunwang-ml/p/11341587.html
评论（0）