网站备案需要当面核验哪些信息,网站建设学习心得,太原建站服务,wordpress 地图相册什么是 LRU
LRU (最近最少使用算法), 最早是在操作系统中接触到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略. LRU算法基于局部性原理, 即最近被访问的数据在未来被访问的概率更高, 因此应该保留最近被访问的数据. 最近最少使用的解释 LRU (最近最少使用算法), 中…什么是 LRU
LRU (最近最少使用算法), 最早是在操作系统中接触到的, 它是一种内存数据淘汰策略, 常用于缓存系统的淘汰策略. LRU算法基于局部性原理, 即最近被访问的数据在未来被访问的概率更高, 因此应该保留最近被访问的数据. 最近最少使用的解释 LRU (最近最少使用算法), 中的 最近 不是其绝对值的修饰, 而是一个范围. 如: 你最近去了那些地方, 最近看了哪些书. 而不是: 离你最近的人是谁, 离你最近的座位是哪一个. 了解了最近的意义, 那么串联起来就是: 最近使用的一堆数据中, 哪一个数据使用的是最少的
LRU原理
下面展示了 LRU 算法的基本原理. 可以看到, 在 LRU 算法中, 涉及到了对象的移动, 如果使用 数组 来作为缓存, 那么移动对象的效率很慢. 因为在这个算法中, 经常涉及到头插元素, 数组 的头插是O(n^2), 非常的慢.
所以推荐使用 双向链表 来实现.
146. LRU 缓存 - 力扣LeetCode
但是在题目中, 要求查找和插入的时间复杂度为O(1); 双向链表的插入删除时间复杂度为O(1), 但是查找的时间复杂度为O(n).
双向链表 哈希表
单使用双向链表, 查找的时间复杂度为O(n), 那么数据结构的查找操作的时间复杂度为O(1)? 答案很明显: 哈希表 定义链表节点 ListNode
struct ListNode
{
public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;// 节点中不仅存储 value, 还存储 key, 这在后面的 put 函数中有用ListNode* next;ListNode* prev;
};
LRUcache 成员属性
class LRUCache {
public:int _size 0; // 记录缓存中已经缓存了多少数据int _capacity 0; // 记录缓存大小 (可缓存的数据个数)ListNode* head nullptr; // 双向链表的头节点ListNode* tail nullptr; // 双向链表的尾节点unordered_mapint, ListNode* table;// 底层是通过 hashtable 实现的map, 用来通过 kev 查找节点
}
LRUcache 成员方法
构造 / get / put 函数
class LRUCache {
public:LRUCache(int capacity) {_capacity capacity; // 记录缓存的大小// 初始化链表的 头节点 和 尾节点head new ListNode;tail new ListNode;// 将头尾节点连接起来head-next tail;head-prev tail;tail-next head;tail-prev head;}// 通过 key 获取对应的 value. 如果 key 不存在, 则返回 -1int get(int key) {auto it table.find(key); // 通过 hashtable 查找 key 是否存在if(it table.end()){return -1; // 不存在对应的 [key, value], 返回 -1}// 存在 key, 记录value, 然后更新这个节点, 将这个节点移动到链表头部int ret it-second-value;MoveToHead(it-second); // 将这个节点移动到头部return ret;}// 插入一对键值对 [key, value]void put(int key, int value) {auto it table.find(key); // 在 hashtable 中查找是否已经存在 keyif(it ! table.end()) // 已经存在 key 则更新节点的值, 并且将这个节点移动到链表头部{// 更新节点it-second-value value;MoveToHead(it-second); // 将节点移动到链表头部return; // 直接返回, 下面是进行插入的操作}// key 不存在, 判断 空间是否已满, 满了就需要删除 链表末尾的节点if(_size _capacity){// ListNode 中记录的 key 就起作用了, 如果只有 value, 那么就还需要遍历 tableint back tail-prev-key;table.erase(back); // 删除 hashtable 中这个节点的记录pop_back(); // 删除尾部节点--_size;}// 链表末尾的节点已被删除, 现在需要向 链表头部 插入 新的节点ListNode* node push_front(key, value);table[key] node; // 在 hashtable 中记录这个新的节点_size;}
};
MoveToHead / push_front / pop_back 函数
class LRUCache {
public:// 将 node 移动到链表头部void MoveToHead(ListNode* node){if(node head-next) // 如果这个节点就是头部, 那么就不移动{return;}ListNode* node_next node-next; // 记录 node 节点的后一个节点ListNode* node_prev node-prev; // 记录 node 节点的前一个节点node_prev-next node_next; // 将 node 的前后节点连接起来node_next-prev node_prev;// 将 node 节点链接到链表首部node-prev head; node-next head-next;head-next-prev node;head-next node;}// 头插ListNode* push_front(int key, int value){ListNode* node new ListNode(key, value);ListNode* next head-next;head-next node;node-prev head;next-prev node;node-next next;return node;}// 尾删void pop_back(){ListNode* prev tail-prev-prev;ListNode* cur tail-prev;prev-next tail;tail-prev prev;delete cur;}
}; 完整代码
class LRUCache {
public:struct ListNode{public:ListNode(){}ListNode(int k, int v):key(k),value(v){}~ListNode(){}int key;int value;ListNode* next;ListNode* prev;};int _size 0;int _capacity 0;ListNode* head nullptr;ListNode* tail nullptr;unordered_mapint, ListNode* table;LRUCache(int capacity) {_capacity capacity;head new ListNode;tail new ListNode;head-next tail;head-prev tail;tail-next head;tail-prev head;}int get(int key) {auto it table.find(key);if(it table.end()){return -1;}int ret it-second-value;MoveToHead(it-second); // 将这个节点移动到头部return ret;}void put(int key, int value) {auto it table.find(key);if(it ! table.end()){// 更新节点it-second-value value;MoveToHead(it-second);return;}if(_size _capacity){int back tail-prev-key;table.erase(back); // 删除 hashtable 中的键值对pop_back(); // 删除尾部节点--_size;}ListNode* node push_front(key, value);table[key] node;_size;}void MoveToHead(ListNode* node){if(node head-next){return;}ListNode* node_next node-next;ListNode* node_prev node-prev;node_prev-next node_next;node_next-prev node_prev;node-prev head;node-next head-next;head-next-prev node;head-next node;}ListNode* push_front(int key, int value){ListNode* node new ListNode(key, value);ListNode* next head-next;head-next node;node-prev head;next-prev node;node-next next;return node;}void pop_back(){ListNode* prev tail-prev-prev;ListNode* cur tail-prev;prev-next tail;tail-prev prev;delete cur;}};
