LRU 缓存

LRU 缓存

问题
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路
使用哈希表、双向链表
使用哈希表保证时间复杂度为O(1)，查找效率高
使用双向链表模拟LRU的队列，最近访问的放在队尾
双向链表的意义在于为哈希表指定了达到容量之后的淘汰策略
哈希表的意义在于返回节点的引用便于双向链表的删除和插入
分别使用

C++实现java原生实现基于linkedHashMap

代码
C++实现

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

class LRUCache {
public:
    int capacity;
    unordered_map mp;
    Node* head;
    Node* tail;

    void removeNode(Node* p){
        p->next->prev=p->prev;
        p->prev->next=p->next;
        p->prev=nullptr;
        p->next=nullptr;
    }
    void addNode(Node* p){
        head->next->prev=p;
        p->next=head->next;
        p->prev=head;
        head->next=p;
    }

    LRUCache(int capacity) {
        this->capacity=capacity;
        head=new Node();
        tail=new Node();
        head->next=tail;
        tail->prev=head;
    }
    
    int get(int key) {
        if(!mp.count(key)){
            return -1;
        }else{

            Node* p=mp[key];
            removeNode(p);
            addNode(p);
            return p->value;
        }
    }
    
    void put(int key, int value) {

        if(mp.count(key)){
            Node* p=mp[key];
            p->value=value;
            mp[key]=p;
            removeNode(p);
            addNode(p);
        }else{
            if(mp.size()==capacity){
                Node* last=tail->prev;
                removeNode(last);
                mp.erase(last->key);
            }
            Node* p=new Node(key,value);
            mp[key]=p;
            addNode(p);
        }

    }
};

Java原生实现

class LRUCache {

    class Node{
        K key;
        V value;
        Node prev;
        Node next;
        public Node(){
            this.prev=this.next=null;
        }
        public Node(K key,V value){
            this.key=key;
            this.value=value;
            this.prev=this.next=null;
        }
    }

    class DoublelinkedList{
        Node head;
        Node tail;

        public DoublelinkedList(){
            head=new Node<>();
            tail=new Node<>();
            head.next=tail;
            tail.prev=head;
        }

        public void addHead(Node node){
            head.next.prev=node;
            node.next=head.next;
            node.prev=head;
            head.next=node;
        }
        public void removeNode(Node node){
            node.prev.next=node.next;
            node.next.prev=node.prev;
            node.next=null;
            node.prev=null;
        }

        public Node getLast(){

            return tail.prev;
        }
    }

    private int capacity;
    Map> map;

    DoublelinkedList doublelinkedList;

    public LRUCache(int capacity) {

        this.capacity=capacity;
        map=new HashMap<>();
        doublelinkedList=new DoublelinkedList<>();
    }
    
    public int get(int key) {

         if(!map.containsKey(key)){
            return -1;
        }

        Node node=map.get(key);
        doublelinkedList.removeNode(node);       // 队列中间删除
        doublelinkedList.addHead(node);         // 添加到队尾

        return node.value;

    }
    
    public void put(int key, int value) {

         if(map.containsKey(key)){

            Node node = map.get(key);
            node.value=value;
            map.put(key,node);        // 更新

            doublelinkedList.removeNode(node);
            doublelinkedList.addHead(node);   // 更新添加到队尾
        }else{

            if(map.size()==capacity){  // 根据底层的DoublelinkedList进行淘汰
                Node node = doublelinkedList.getLast();
                map.remove(node.key);
                doublelinkedList.removeNode(node);
            }
            Node node = new Node<>(key, value);
            map.put(key,node);
            doublelinkedList.addHead(node);
        }

    }
}

基于linkedHashMap

class LRUCache {

    int capacity;
    linkedHashMap map;

    public LRUCache(int capacity){
        this.capacity=capacity;
        map=new linkedHashMap(capacity,0.75f,true){

            @Override
            protected boolean removeEldestEntry(Map.Entry eldest){
                return map.size()>capacity;
            }
        };
    }
    public int get(int key){
        if(map.containsKey(key)){
            return map.get(key);
        }else
        return -1;
    }
    public void put(int key,int value){
        map.put(key,value);
    }
}