LRU Cache
一、什么是LRU Cache
LRU是Least Recently Used的缩写，意思是最近最少使用，它是一种Cache替换算法。
什么是Cache？狭义的Cache指的是位于CPU和主存间的快速RAM， 通常它不像系统主存那样使用DRAM技术，而使用昂贵但较快速的SRAM技术。 广义上的Cache指的是位于速度相差较大的两种硬件之间， 用于协调两者数据传输速度差异的结构。除了CPU与主存之间有Cache， 内存与硬盘之间也有Cache，乃至在硬盘与网络之间也有某种意义上的Cache── 称为Internet临时文件夹或网络内容缓存等。
Cache的容量有限，因此当Cache的容量用完后，而又有新的内容需要添加进来时， 就需要挑选并舍弃原有的部分内容，从而腾出空间来放新内容。LRU Cache 的替换原则就是将最近最少使用的内容替换掉。其实，LRU译成最久未使用会更形象， 因为该算法每次替换掉的就是一段时间内最久没有使用过的内容。
二、LRU Cache的实现
实现LRU Cache的方法和思路很多，但是要保持高效实现O(1)的put和get，那么使用双向链表和哈希表的搭配是最高效和经典的。使用双向链表是因为双向链表可以实现任意位置O(1)的插入和删除，使用哈希表是因为哈希表的增删查改也是O(1)。
我们以LeetCode上的一道题来实现LRU Cache
这道题要求使用O(1)的时间复杂度来完成get和put的操作，我们最先想到的是使用哈希表，这样查找的时间复杂度就是O(1)，我们还需要一个链表来保存节点，如果链表保存的是key和val，完成数据的更新操作，即将链表中key的位置移到头部，更新顺序，但是更新的时候需要遍历查找key，此时的时间复杂度为O(N)，就不能满足O(1)的要求，我们需要找到key，就要找到key对应存储数据在链表中的位置，此时我们可以将哈希表的value改为链表的迭代器，这样找到key，就可以得到链表的迭代器，就可以完成更新操作
第一种方式我们自己实现一个链表
struct Node
{
int key;
int val;
Node* prev;
Node* next;
Node():key(0),val(0),prev(nullptr),next(nullptr){}
Node(int _key,int _val):key(_key),val(_val),prev(nullptr),next(nullptr){}
};
class LRUCache
{
private:
unordered_map<int,Node*> cache;
Node* head;
Node* tail;
int size;
int capacity;
public:
LRUCache(int _capacity)
:capacity(_capacity),size(0)
{
// 使用伪头部和伪尾部节点
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key)
{
if(!cache.count(key)) return -1;
// 如果 key 存在，先通过哈希表定位，再移到头部
Node* node = cache[key];
moveToHead(node);
return node->val;
}
void put(int key, int value)
{
// 如果 key 不存在，创建一个新的节点
if(!cache.count(key))
{
Node* node = new Node(key,value);
// 添加进哈希表
cache[key] = node;
// 添加至双向链表的头部
addToHead(node);
++size;
if(size > capacity)
{
// 如果超出容量，删除双向链表的尾部节点
Node* removed = removeTail();
// 删除哈希表中对应的项
cache.erase(removed->key);
delete removed;
--size;
}
}
else
{
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
Node* node = cache[key];
node->val = value;
moveToHead(node);
}
}
void addToHead(Node* node)
{
node->next = head->next;
head->next->prev = node;
node->prev = head;
head->next = node;
}
void removeNode(Node* node)
{
node->prev->next = node->next;
node->next->prev = node->prev;
}
void moveToHead(Node* node)
{
removeNode(node);
addToHead(node);
}
Node* removeTail()
{
Node* node = tail->prev;
removeNode(node);
return node;
}
};
第二种方式使用STL库中的链表
class LRUCache
{
private:
typedef list<pair<int,int>>::iterator iter;
list<pair<int,int>> _LRUList;
unordered_map<int,iter> _hashMap;
int _capacity;
public:
LRUCache(int capacity)
:_capacity(capacity)
{}
int get(int key)
{
auto ret = _hashMap.find(key);
if(ret == _hashMap.end()) return -1;
//使用splice函数进行移动节点
iter it = ret->second;
_LRUList.splice(_LRUList.begin(),_LRUList,it);
return it->second;
}
void put(int key, int value)
{
auto ret = _hashMap.find(key);
if(ret != _hashMap.end())
{
// 没有找到就更新节点的值,将其移动到链表的头部
iter it = ret->second;
it->second = value;
_LRUList.splice(_LRUList.begin(),_LRUList,it);
}
else
{
//如果满了就先删除链表的尾部节点
if(_capacity == _hashMap.size())
{
pair<int,int> back = _LRUList.back();
_hashMap.erase(back.first);
_LRUList.pop_back();
}
_LRUList.push_front(make_pair(key,value));
_hashMap[key] = _LRUList.begin();
}
}
};
std::list::splice介绍
splice是std::list容器的一个成员函数，用于将另一个std::list中的元素移动到当前list的指定位置。它的语法如下：
cppCopy Codevoid splice (iterator position, list& x);
void splice (iterator position, list& x, iterator it);
void splice (iterator position, list& x, iterator first, iterator last);
参数说明：
- position：指定插入位置的迭代器。
- x：另一个std::list容器。
- it：指向x中某个元素的迭代器，表示要移动的元素。
- first, last：表示要移动的元素范围，包括first但不包括last。
使用splice函数可以实现以下操作：
- 将另一个std::list中的所有元素移动到当前list的指定位置。
- 将另一个std::list中的某个元素移动到当前list的指定位置。
- 将另一个std::list中指定范围的元素移动到当前list的指定位置。
移动元素后，原来的std::list容器将不再包含这些元素，而被移动的元素将被插入到当前list的指定位置。
注意事项：
- 使用splice函数时，被移动的元素会保持原来的顺序。
- 被移动的元素将从原来的list中删除，插入到当前list中。
- 如果移动的元素与当前list中的元素类型不兼容，会导致编译错误。
原文地址：https://blog.csdn.net/qq_67582098/article/details/142371317
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！