数据结构:缓存淘汰策略
文章目录
三种缓存淘汰策略单链表实现LRU数组实现LRU
三种缓存淘汰策略
1.FIFO - First In First Out - 先进先出 2.LFU - Least Frequently Used - 最少 - 使用 3.LRU - Least Recently Used - 最近 - 最少 - 使用
其中LRU使用最广,下面介绍 使用 链表 和 数组 来实现LRU
单链表实现LRU
(1)当访问的数据 - 没有存在 - 于存储缓存的链表中时: i- 如果缓存链表没满:将数据插入链表表头,时间复杂度为 O(1); ii - 如果缓存链表满了:删除链表的末位,将新数据添加到 缓存链表 的表头,时间复杂度为 O(1)。
(2)当访问的数据 - 存在于 - 存储缓存的链表中时: 将该数据对应的节点,调整到链表表头,时间复杂度为 O(1)。
缓存链表满,从链表尾部开始清理
数据结构:缓存淘汰策略最先出现在Python成神之路。
共有 0 条评论