Leetcode（146）——LRU cache

subject

Please design and implement a meeting LRU ( Recently at least use ) cache Constrained data structure .
Realization LRUCache class ：

• LRUCache(int capacity) With Positive integer As capacity capacity initialization LRU cache
• int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
• void put(int key, int value) If the keyword key Already exist , Change its data value value ; If it doesn't exist , Then insert the group into the cache key-value . If the insert operation causes the number of keywords to exceed capacity , Should be Eviction The longest unused keyword .

function get and put Must be $O(1)$ The average time complexity of running .

Example ：

Input
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
explain
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // The cache is {1=1}
lRUCache.put(2, 2); // The cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // This operation causes the keyword to 2 To void , The cache is {1=1, 3=3}
lRUCache.get(2); // return -1 ( Not found )
lRUCache.put(4, 4); // This operation causes the keyword to 1 To void , The cache is {4=4, 3=3}
lRUCache.get(1); // return -1 ( Not found )
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

Tips ：

• $1$ <= capacity <= $3000$
• $0$ <= key <= $10000$
• $0$ <= value <= $10^5$
• Call at most $2\ast 10^5$ Time get and put

Answer key

Method 1 ： Hashtable + Double linked list

Ideas

​​  LRU The cache mechanism can be realized by hash table supplemented by bidirectional linked list , We use a hash table and a two-way linked list to maintain all key value pairs in the cache .

• The bidirectional list stores these key value pairs in the order they are used , The key value pair near the head is the most recently used , The key value pairs near the tail are the most unused .
• A hash table is a common hash map （HashMap）, The key of the cached data is mapped to its position in the bidirectional linked list .

Since then , We first use a hash table for positioning , Find the location of the cache item in the bidirectional linked list , Then move it to the head of the bidirectional list , Can be in $O(1)$ In time to complete get perhaps put operation . The specific method is as follows ：

• about get operation , First judgement key Whether there is ：
  • If key non-existent , Then return to $-1$;
  • If key There is , be key The corresponding node is the most recently used node . Locate the position of the node in the bidirectional linked list through the hash table , And move it to the head of the two-way linked list , Finally, the value of the node is returned .
• about put operation , First judgement key Whether there is ：
  • If key non-existent , Use key and value Create a new node , Add the node to the head of the double linked list , And will key And the node is added to the hash table . Then judge whether the number of nodes in the two-way linked list exceeds the capacity , If the capacity is exceeded , Delete the tail node of the bidirectional linked list , And delete the corresponding item in the hash table ;
  • If key There is , Then with get The operation is similar to , First, locate through the hash table , Then update the value of the corresponding node to value, And move the node to the head of the bidirectional linked list .

Of the above operations , The time complexity of accessing the hash table is $O(1)$, Add a node at the head of the two-way linked list 、 The complexity of deleting nodes at the end of the two-way linked list is also $O(1)$. And move a node to the head of the two-way linked list , Can be divided into 「 Delete the node 」 and 「 Add a node at the head of the two-way linked list 」 Two step operation , Can be in $O(1)$ Within time .

Why data structures are used

• Why not use a single linked list ？ Because if get When the operation accesses a node in the middle of the linked list , Using a two-way linked list, you can quickly get the addresses of the previous node and the next node , And connect them .
• Why do bi-directional linked lists store key？ Because when inserting a new value , If the length of the linked list is equal to capacity , Delete the key value pairs in the hash table , At this point, you need to get the longest unused key value to call erase function .
• The structure of the hash table is unordered_map<int, ListNode*>, To quickly find the corresponding key-value , At the same time, because the storage is ListNode*, So you can update the linked list again .

Tips:

In the realization of bidirectional linked list , Use one Pseudo head （dummy head） and Pseudo tail （dummy tail） Mark the boundaries , In this way, there is no need to check whether adjacent nodes exist when adding or deleting nodes .

Code implementation

My own ：

class LRUCache {
    
    //  Bidirectional linked list storage usage 
    typedef struct dataUse{
    
        //  The two-way linked list is stored in a group  key-value, Because in excess of capacity To delete hashmap in key-value pair  when .
        //  Must pass Node Inside key To delete ,hashmap Unable to get value To delete 
        int key;
        int value;
        //  When get When you need to access the element whose usage is in the middle , Its previous and subsequent elements are required to facilitate reconnection 
        struct dataUse *next;
        struct dataUse *last;
        dataUse():key(-1), value(-1), next(nullptr), last(nullptr){
    }
        dataUse(int k, int v, struct dataUse *nextone, struct dataUse *lastone):
            key(k), value(v), next(nextone), last(lastone){
    }
    }DU;
    //  The hash table stores its corresponding address in the linked list 
    unordered_map<int, DU*> cache;
    DU *h, *t;  //  Head and tail , among  h->next  Indicates the latest unused keyword 
    int maxsize;

    void movetoT(DU *p){
    
        p->last->next = p->next;
        p->next->last = p->last;
        p->last = t->last;
        p->next = t;
        t->last->next = p;
        t->last = p;
    }

    void addtoT(int key, int value){
    
        t->last->next = new DU(key, value, t, t->last);
        t->last = t->last->next;
    }

public:
    LRUCache(int capacity):h(new DU), t(new DU), maxsize(capacity){
    
        h->next = t;
        t->last = h;
    }
    
    int get(int key) {
    
        if(cache.count(key) == 0) return -1;
        else{
    
            if(t->last != cache[key]) movetoT(cache[key]);
            return cache[key]->value;
        }
    }
    
    void put(int key, int value) {
    
        if(cache.count(key) == 0){
    
            if(cache.size() == maxsize){
    
                cache.erase(h->next->key);    //  Delete the key pairs in the hash table that have not been used for too long 
                cache.emplace(key, h->next);
                cache[key]->key = key;
                cache[key]->value = value;
                movetoT(cache[key]);
            }else{
    
                addtoT(key, value);
                cache.emplace(key, t->last);
            }
        }else{
    
            if(t->last != cache[key]) movetoT(cache[key]);
            cache[key]->value = value;
        }
    }
};

/** * 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); */

Leetcode Official explanation ：

struct DLinkedNode {
    
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {
    }
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {
    }
};

class LRUCache {
    
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;

public:
    LRUCache(int _capacity): capacity(_capacity), size(0) {
    
        //  Using pseudo head and pseudo tail nodes 
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
    
        if (!cache.count(key)) {
    
            return -1;
        }
        //  If  key  There is , First, locate through the hash table , And then to the head 
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
    
        if (!cache.count(key)) {
    
            //  If  key  non-existent , Create a new node 
            DLinkedNode* node = new DLinkedNode(key, value);
            //  Add to hash table 
            cache[key] = node;
            //  Add to the head of the bidirectional list 
            addToHead(node);
            ++size;
            if (size > capacity) {
    
                //  If the capacity is exceeded , Delete the tail node of the bidirectional linked list 
                DLinkedNode* removed = removeTail();
                //  Delete the corresponding entry in the hash table 
                cache.erase(removed->key);
                //  Prevent memory leaks 
                delete removed;
                --size;
            }
        }
        else {
    
            //  If  key  There is , First, locate through the hash table , Revise  value, And move to the head 
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void addToHead(DLinkedNode* node) {
    
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(DLinkedNode* node) {
    
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void moveToHead(DLinkedNode* node) {
    
        removeNode(node);
        addToHead(node);
    }

    DLinkedNode* removeTail() {
    
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

Netizen explanation ：

struct lrunode{
    
    int val;
    int key;
    lrunode* next;
    lrunode* last;
};

class LRUCache {
    
public:
    lrunode* mp[10001];
    lrunode *list,*tail;
    int capacity;
    int size;
    LRUCache(int capacity) {
    
        for(int i=0;i<10001;++i)mp[i] = nullptr;
        this->capacity = capacity;
        list = tail = nullptr;
        size = 0;
    }
    
    int get(int key) {
    
        if(mp[key]!=nullptr){
    
            lrunode* t = mp[key];
            used(t);
            return t->val;
        }
        else return -1;
    }
    
    void put(int key, int value) {
    
        if(mp[key]!=nullptr){
    
            lrunode* t = mp[key];
            t->val = value;
            used(t);
        }else{
    
            lrunode* node = new lrunode;
            node->key = key;
            node->val = value;
            mp[key] = node;
            push_front(node);
            if(size<capacity){
    
                size++;
            }else{
    
                pop_back();
            }
        }
    }

    void used(lrunode* t){
    
        if(t==list)return;
        if(t->last)t->last->next = t->next;
        if(t->next)t->next->last = t->last;
        else tail = t->last;
        t->last = nullptr;
        t->next = list;
        if(list)list->last = t;
        list = t;
        if(tail == nullptr)tail = t;
    }

    void push_front(lrunode* node){
    
        node->last = nullptr;
        node->next = list;
        if(list)list->last = node;
        list = node;
        if(tail == nullptr)tail = node;
    }

    void pop_back(){
    
        lrunode* t = tail;
        if(list == tail){
    
            list = tail = nullptr;
        }else{
    
            tail = tail->last;
            tail->next = nullptr;
        }
        mp[t->key] = nullptr;
        delete t;
    }
};

Complexity analysis

Time complexity ： about put and get All are $O(1)$.
Spatial complexity ：$O(capacity)$, Because hash tables and bidirectional linked lists store the most $2\ast \text{capacity}+2$ Elements .