LRU最近最少使用代码实现

LRU是指长期没有被使用的数据在未来使用的概率不大,当数据所占内存达到一定的阈值,要移除最近最少使用的数据,为新加入的数据腾出空间。

LRU使用哈希+链表的结构,如图所示,我们假设容量为2,依次插入数据1和数据2;

LRU最近最少使用代码实现

当访问了某个结点,就将结点放在链表的最右端。如图所示我们访问了结点1,就将结点1移到链表的最右端。

LRU最近最少使用代码实现

当达到了容量上限再插入新数据时,就将最近最少使用的数据移除,如图所示,我们插入结点3,在插入之前将结点2移出去。

LRU最近最少使用代码实现

详细代码如下: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 }

 

上一篇:201521123117 《Java程序设计》第2周学习总结


下一篇:如何实现LRU缓存?