LRU算法 C++实现（HashMap+双向链表）

LRU算法 C++实现（HashMap+双向链表）

leetcode上测试代码的题目
LRU（最近最少使用算法），是缺页置换解决方法中的一种。时间复杂度优秀O（1），空间复杂度不算哈希表本身的消耗的话还会多出维护双向链表左右指针的2N大小的空间消耗。
具体实现方法就是在原有数据结构（一般是哈希表）的基础上套上一个双向链表。当 *** 作（询问，修改，增加）某个链表中某个元素的时候把这个元素移动到链表头上。当缓存区满了的时候去掉链表尾上的那个元素即可。
代码实现（HashSet和双向链表都是自实现的）：

class LRUCache {
public:
    static const int P = 1217;
    struct Node{
        int key,value;
        Node *left;
        Node *right;
        Node(int _key,int _value,Node *_left,Node *_right){
            key = _key;
            value = _value;
            left = _left;
            right = _right;
        };
    };
    int capacity,size;
    vector hashset[P];
    Node *head = NULL,*tail = NULL;
    int hash(int key){
        return key%P;
    }
    LRUCache(int _capacity) {
        capacity = _capacity;
        head = tail = NULL;
        size = 0;
    }
    
    int get(int key) {
        int hs = hash(key);
        for(auto x:hashset[hs]){
            if(x->key == key){
                update(x,x->value);
                return x->value;
            }
        }
        return -1;
    }

    void remove(int key){
        int hs = hash(key);
        for(int i = 0;i < hashset[hs].size();++i){
            if(hashset[hs][i]->key == key){
                tail = tail->left;
                if(size == 1) tail = head = NULL;
                size--;
                merge(hashset[hs][i]->left,hashset[hs][i]->right);
                hashset[hs].erase(hashset[hs].begin()+i);
                return;
            }
        }
    }

    void merge(Node *L,Node* R){
        if(L != NULL) L->right = R;
        if(R != NULL) R->left = L;
    }

    void update(Node *now,int value){
        if(size > 1 && tail == now) tail = tail->left;
        now->value = value;
        if(now == head) return;
        merge(now->left,now->right);
        merge(now,head);
        head = now;
    }

    void insert(int hs,int key,int value){
        size++;
        Node *newnode = new Node(key,value,NULL,NULL);
        hashset[hs].push_back(newnode);
        if(head == NULL){
            head = newnode;
            tail = newnode;
        }else{
            merge(newnode,head);
            head = newnode;
        }
    }
    
    void put(int key, int value) {
        int hs = hash(key);
        for(int i = 0;i < hashset[hs].size();++i){
            if(hashset[hs][i]->key == key){
                update(hashset[hs][i],value);
                return;
            }
        }
        if(size < capacity){
            insert(hs,key,value);
            return;
        }
        remove(tail->key);
        insert(hs,key,value);
    }
};