146. LRU缓存机制

 

---

/*
采用哈希链表的方法，集合了哈希表的查找高效，和链表的删除插入高效的特点
哈希表存储键值，和键值对应的双向链表的节点，
链表中存储键值，和value值
*/

//建立一个双向链表的节点
struct listnode{
    int val;
    int key;
    listnode *pre;
    listnode *next;
    listnode(int _key,int _val):key(_key),val(_val),pre(NULL),next(NULL){}
    listnode():key(0),val(0),pre(NULL),next(NULL){}
};//分号不要忘记

class LRUCache {
    //能够容纳的大小
    int capacity;
    //目前含有的数量
    int size;
    unordered_map<int,listnode*>record;
    listnode*head;
    listnode*tail;
    
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
        size=0;
        //建立一个头节点，尾节点
        head=new listnode();
        tail=new listnode();
        //头节点尾节点指向的初始化
        head->next=tail;
        tail->pre=head;
    }
    
    int get(int key) {

        // 如果 key 存在，先通过哈希表定位，再移到头部
        if(record.count(key)==true)
        {
            listnode*node=record[key];
            moveToHead(node);
            return node->val;
            

        }
        else return -1;
    }
    
    void put(int key, int value) {
        
        //判断key存在哈希表中
        if(record.count(key)==true)
        {
            //如果key存在哈希表中，先通过哈希表定位，再修改value,并且移动到头部
            listnode *node=record[key];
            node->val=value;
            moveToHead(node);

        }
        else//key不存在哈希表中，新建一个节点，将节点加入哈希表中，再将节点加入到链表头中，如果size大小大于capacity,则删除尾节点
        {
            //key不存在哈希表中，新建一个节点
            listnode*node=new listnode(key,value);
            //添加到哈希表中
            record[key]=node;
            //添加到链表头中
            addToHead(node);
            size++;
            //链表已满、哈希表已满
            if(size>capacity)
            {
                //超出容量，删除伪节点
                listnode* removed=remove_tail();
                //删除哈希表中对应的项
                record.erase(removed->key);
                //防止内存泄漏
                delete removed;
                size--;

            }

        }

    }
    void addToHead(listnode*node)
    {
        //向一个双向链表中添加一个链表节点
        node->pre=head;
        node->next=head->next;
        head->next->pre=node;
        head->next=node;

    }
    //从列表中 “移出” 这个节点，并非删除
    void removeNode(listnode*node)
    {
        node->pre->next=node->next;
        node->next->pre=node->pre;

        node->pre=NULL;
        node->next=NULL;
    }
    //将节点移动到头节点，分成两步，将节点移出链表，再将节点加入到头节点
    void moveToHead(listnode*node)
    {
        removeNode(node);
        addToHead(node);
    }
    //删除尾节点
    listnode* remove_tail()
    {
        //先用指针指向尾节点的头一个节点
        listnode*node=tail->pre;
        removeNode(tail->pre);
        return  node;
    }

};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */