漳州企业网站建设公司网站建设条例

漳州企业网站建设公司,网站建设条例,蚂蚁网站建设,移动积分兑换商城官方网站1.什么是LRU缓存 LRU缓存是一种常见的缓存淘汰算法#xff0c;用于在缓存空间不足时#xff0c;决定哪些数据应该被移除。它的核心思想是#xff1a;当缓存已满时#xff0c;优先淘汰最近最少使用的数据。 2.核心原理 假设缓存空间有限#xff0c;只能存储固定数量的数据…1.什么是LRU缓存LRU缓存是一种常见的缓存淘汰算法用于在缓存空间不足时决定哪些数据应该被移除。它的核心思想是当缓存已满时优先淘汰最近最少使用的数据。2.核心原理假设缓存空间有限只能存储固定数量的数据项。当需要添加新数据但缓存已满时(1)系统会检查缓存中所有数据(2)选择最近最久没有被访问的数据(3)将其移除腾出空间给新数据3.为什么需要LRU缓存缓存空间有限不可能存储所有数据遵循“局部性原理”最近被访问的数据未来再次被访问的概率更高通过保留热点数据提高缓存命中率4.思路既然LRU缓存的核心是移除最久未访问过的数据那么我们就得考虑应该如何确定哪个数据是最久未访问的。可以使用双向链表加哈希表每次有新的数据加入时将其加入链表的第一个节点当访问一个节点后将其移到链表的第一个节点。这样操作后当超过缓存大小时链表的最后一个节点就一定是最久未访问过的数据。所以当加入一个数据后超过了缓存大小我们就可以直接删除最后一个节点这样删除的一定是最久未访问过的数据.而哈希表的配合使用可以让我们在访问节点时仅需On的时间复杂度可以提高我们的查找效率当新数据加入缓存时将其也同步加入哈希表中同样的删除数据时也从哈希表中删除对应数据。通过这种方法我们就实现了LRU缓存的核心原理并且也有最佳的查找效率。5.实现方式(1)使用一个双向链表,定义两个指针一个指向前一个节点一个指向后一个节点。//结构体创建 struct Node{ Node* next;//指向后一个节点 Node* prev;//指向前一个节点 int val;//数据值 int key;//数据键 Node(){ this-val 0; this-key 0; this-next nullptr; this-prev nullptr; } Node(int val,int key){ this-val val; this-key key; this-next nullptr; this-prev nullptr; } };(2)初始化成员变量int capacity;//缓存大小 int size;//当前大小 unordered_mapint,Node*mp;//哈希表 Node* head;//链表虚拟头节点 Node* tail;//链表虚拟尾节点(3)当有新数据加入缓存中时每次都将其插入到第一个节点中void addHead(Node* p){ p-next head-next; head-next p; p-next-prev p; p-prev head; }(4)当访问过一个数据时,将其移动到链表头部①先将其从链表中取出②将其添加到链表头部//从链表中取出节点 void delNode(Node* p){ p-prev-next p-next; p-next-prev p-prev; } //加入链表头部 void moveHead(Node* p){ delNode(p);//调用函数从链表中取出 addHead(p);//添加到链表头部 }(5)当超出缓存大小时,将尾部节点删除!!注意!!:要将删除的节点内存释放,而且要防止内存泄露void delTail(){ Node* node tail-prev;//获取要删除的节点 mp.erase(node-key);//从哈希表中同步删除 delNode(node);//调用方法删除节点 delete node;//释放内存,防止内存泄露 node nullptr;//避免野指针 }(6)LRU缓存初始化class LRUCache { public: LRUCache(int capacity) { head new Node(); tail new Node(); head-next tail; tail-prev head; this-capacity capacity; this-size 0; } }(7)访问数据时①判断该节点是否存在(哈希表)②用一个变量接收节点③将其移到链表第一个节点④返回该节点的数据值int get(int key) { //判断是否存在 if(mp.find(key)mp.end()){ return -1; } //接收该节点 Node* node mp[key]; //移动到第一个节点位置 moveHead(node); //返回数据值 return node-val; }(8)加入新数据时①判断节点是否已经存在②得到节点③判断是否超出缓存大小,如果超出就删除最后一个节点④若节点不存在,则插入链表第一个节点位置,并加入哈希表中;若已经存在,则修改该节点的数据值,并将其移到链表第一个位置void put(int key, int value) { //如果不存在 if(mp.find(key)mp.end()){ //创建新节点 Node* node new Node(value,key); size;//更新当前缓存大小 //判断是否超出缓存大小 if(sizecapacity){ delTail();//删除最后一个节点 } addHead(node);//加入第一个节点 mp[key] node;//加入哈希表中 } //如果存在 else{ Node* node mp[key];//得到节点 node-val value;//更新数据值 moveHead(node);//移动到第一个节点的位置 } }6.完整代码实现class LRUCache { //结构体定义 struct Node{ Node* next; Node* prev; int val; int key; Node(){ this-val 0; this-key 0; this-next nullptr; this-prev nullptr; } Node(int val,int key){ this-val val; this-key key; this-next nullptr; this-prev nullptr; } }; private: int capacity; int size; unordered_mapint,Node*mp; Node* head; Node* tail; //添加到头部 void addHead(Node* p){ p-next head-next; head-next p; p-next-prev p; p-prev head; } //移动到头部 void moveHead(Node* p){ delNode(p); addHead(p); } //删除节点 void delNode(Node* p){ p-prev-next p-next; p-next-prev p-prev; } //删除尾部节点 void delTail(){ Node* node tail-prev; mp.erase(node-key); delNode(node); delete node; node nullptr; } public: //初始化 LRUCache(int capacity) { head new Node(); tail new Node(); head-next tail; tail-prev head; this-capacity capacity; this-size 0; } //访问数据 int get(int key) { if(mp.find(key)mp.end()){ return -1; } Node* node mp[key]; moveHead(node); return node-val; } //插入数据 void put(int key, int value) { if(mp.find(key)mp.end()){ Node* node new Node(value,key); size; if(sizecapacity){ delTail(); } addHead(node); mp[key] node; }else{ Node* node mp[key]; node-val value; moveHead(node); } } };7.总结LRU缓存是一种基于时间局部性原理的经典缓存管理策略通过“淘汰最久未用数据”来最大化缓存效用。虽然在高并发或特殊访问模式下可能不是最优选择但其简单有效的特性使其成为应用最广泛的缓存算法之一。