首页 > 代码库 > LRU Cache

LRU Cache

2024-08-17 04:46:46   221人阅读

题意：

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

学LRU是在操作系统中，最近最久未被使用的，根据cache的大小，每当有一个进程来到时，都要根据当前的情况而做一些改变。

set：如果当前来到的key在cache中，则将该节点删除并且移到链表的头部，如果不存在，并且当前的cache满了，则将尾部删除，将新来的节点加入到链表的首部，否则直接加入练表中即可。

get：如果当前的key在cache中，则将该节点从链表中移除并且添加带链表的首部并返回value，否则返回－1。

代码给的是用hashmap和双链表完成的，因为当删除一个节点的时候，需要知道他的后记节点，虽然单链表也能做到这一点，但是如果要删除的节点是尾节点，那么就要知道他的前一个节点，这样的话就要便利整个链表，那么就会花o(n)的时间复杂度，虽然说当链表中有n个节点，那么(o(1)*(n-1) + o(n))/n这样平均的话时间复杂度是在o(1)的，但是也可以彻底做到时间复杂度是o(1)的，就用双链表，会将首位标记出来。

 
struct Linklist
{
    int key;
    int value;
    struct Linklist* pre;
    struct Linklist* next;
};

class LRUCache
{
private:
    int count;
    int size;
    struct Linklist* tail;
    struct Linklist* head;
    map<int,Linklist*>mp;
public:
    LRUCache(int size)
    {
        this->size = size;
        this->tail = NULL;
        this->head = NULL;
        this->count = 0;
    }
    //如果该节点在map中存在，则删除当前的，并改变节点的值，将该节点放在双链表的表头
    //否则返回-1
    int get(int key)
    {
        if(head == NULL) return -1;
        map<int,Linklist*>::iterator it = mp.find(key);
        if(it == mp.end()) 
        {
            return -1;
        } 
        else 
        {
            Linklist *p = it->second;
            pushup(p);
        }
        return head->value;
    }
    //双链表删除节点 然后放在双链表的表头
    void pushup(Linklist* p)
    {
        if(this->count == 1) return ;
        if(p == this->head) return;
        if(p == this->tail) 
        {
            tail = p->pre;
        }
        p->pre->next = p->next;
        if(p->next != NULL)
            p->next->pre = p->pre;

        p->next = head;
        p->pre = NULL;
        head->pre = p;
        head = p;
    }
    //当前值，没有在cache中  则删除链表中最后一个节点&&map中删除，然后将访问的节点加在链表的表头
    //没有在cache中，则将尾删除  将新的元素入链表  并将元素加入到map中
    void  set(int key,int value)
    {
        if(head == NULL)
        {
            head = (Linklist *)malloc(sizeof(Linklist));
            head->value =http://www.mamicode.com/ value;
            head->key = key;
            head->pre = NULL;
            head->next = NULL;
            mp[key] = head;
            tail = head;
            this->count++;
        }
        else
        {
            map<int,Linklist*>::iterator it = mp.find(key);
            if(it == mp.end()) 
            {
                if(size == count)
                {
                    if(size == 1 && tail == head) //size == 1
                    {
                        mp.erase(head->key);
                        head->key = key;
                        head->value =http://www.mamicode.com/ value;
                        mp[head->key] = head;
                    }
                    else //满
                    {
                        Linklist *p = tail;
                        tail->pre->next = p->next;
                        mp.erase(tail->key);
                        tail = tail->pre;
                        p->key = key;
                        p->value =http://www.mamicode.com/ value;
                        p->next = head;
                        head->pre = p;
                        head = p;
                        mp[head->key] = head;

                    }    
                }
                else
                {
                    Linklist *p = (Linklist*)malloc(sizeof(Linklist));
                    p->value =http://www.mamicode.com/ value;
                    p->key = key;
                    p->next = head;
                    p->pre = NULL;
                    head->pre = p;
                    head = p;
                    mp[head->key] = head;
                    this->count++;
                }
            }
            else
            {
                Linklist *p = it->second;
                p->value =http://www.mamicode.com/ value;
                pushup(p);
            }
        }
    }
};

lala

LRU Cache


联系
我们