LRU是指长期没有被使用的数据在未来使用的概率不大,当数据所占内存达到一定的阈值,要移除最近最少使用的数据,为新加入的数据腾出空间。
LRU使用哈希+链表的结构,如图所示,我们假设容量为2,依次插入数据1和数据2;
当访问了某个结点,就将结点放在链表的最右端。如图所示我们访问了结点1,就将结点1移到链表的最右端。
当达到了容量上限再插入新数据时,就将最近最少使用的数据移除,如图所示,我们插入结点3,在插入之前将结点2移出去。
详细代码如下:get()用来访问元素,set()用来添加元素。
class LRU { public: LRU(int k):m_capcity(k){}; list<int>mylist; unordered_map<int, pair<int, list<int>::iterator>>hashmap; void insert(int key,int value) { mylist.push_back(key); hashmap[key]=make_pair(value, --mylist.end()); } int get(int key) //每访问一次将该结点移到链表最右边 { auto it=hashmap.find(key); //在哈希表中找key if(it!=hashmap.end())//找到了 { mylist.erase(it->second.second); //删除链表当前结点 mylist.push_back(key);//重新在尾部删除 hashmap[key].second=(--mylist.end());
//修改哈希表中的指针部分,让它重新指向链表的尾部 return it->second.first; } return -1; } void set(int key,int value) { if(get(key)!=-1)//原来链表中有key,只需修改value { hashmap[key].first=value; return; } if(hashmap.size()<m_capcity)//还有空间,直接插入 insert(key, value); else//将链表最左边的结点连同哈希表结点一起删除 { int removekey=mylist.front(); mylist.pop_front(); hashmap.erase(removekey); insert(key, value); } } private: int m_capcity }