LRU Cache

时间：2019-08-12 18:19:34 阅读：118 评论：0 收藏：0 [点我收藏+]

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)

评论一句话评论（0）

分享档案

更多>