146. LRU 缓存机制

男娘i 2022-10-10 06:02 214阅读 0赞

> 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。  
> 实现 LRUCache 类：
> 
> LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存  
> int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。  
> void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。  
>

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

> Node
> 
>     class Node{
>         //Node属性有 key val  前驱节点  后继节点
>         int key,val;
>         Node prev,next;
>         public Node(int key,int val){
>             this.key=key;
>             this.val=val;
>         }
>     }
> 
> **双向链表思路**
> 
>     class DoubleList {  
>     
>          //属性: 头结点 尾结点 长度
>         Node head , tail;
>         int size;
>     
>         // 在链表头部添加节点 x，时间 O(1)
>         public void addFirst(Node x);
>     
>         // 删除链表中的 x 节点（x 一定存在）
>         // 由于是双链表且给的是目标 Node 节点，时间 O(1)
>         public void remove(Node x);
>         
>         // 删除链表中最后一个节点，并返回该节点，时间 O(1)
>         public Node removeLast();
>         
>         // 返回链表长度，时间 O(1)
>         public int size();
>     }
> 
> **LRU思路;**
> 
>     int get(int key) {
>         if (key 不存在) {
>             return -1;
>         } else {        
>             将数据 (key, val) 提到开头；
>             return val;
>         }
>     }
>     
>     void put(int key, int val) {
>         Node x = new Node(key, val);
>         if (key 已存在) {
>             把旧的数据删除；
>             将新节点 x 插入到开头；
>         } else {
>             if (cache 已满) {
>                 删除链表的最后一个数据腾位置；
>                 删除 map 中映射到该数据的键；
>             } 
>             将新节点 x 插入到开头；
>             map 中新建 key 对新节点 x 的映射；
>         }
>     }

class Node {
        public int key, val;
        public Node next, prev;
        public Node(int k, int v) {
            this.key = k;
            this.val = v;
        }
    }
    class DoubleList {
    
        private Node head, tail;
        private int size;
    
        public void addFirst(Node node) {
            if (head == null) {
                head = tail = node;
            } else {
                Node n = head;
                n.prev = node;
                node.next = n;
                head = node;
            }
            size++;
        }
    
        public void remove(Node node) {
            if (head == node && tail == node) {
                head = null;
                tail = null;
            } else if (tail == node) {
                node.prev.next = null;
                tail = node.prev;
            } else if (head == node) {
                node.next.prev = null;
                head = node.next;
            } else {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            size--;
        }
    
        public Node removeLast() {
            Node node = tail;
            remove(tail);
            return node;
        }
    
        public int size() {
            return size;
        }
    }
    
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        put(key, val);
        return val;
    }
    
    public void put(int key, int value) {
        Node x = new Node(key, value);
    
        if (map.containsKey(key)){
            cache.remove(map.get(key));
            cache.addFirst(x);
            map.put(key,x);
        } else {
            if (cap == cache.size()) {
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            cache.addFirst(x);
            map.put(key,x);
        }
    }

**全部代码: **

class LRUCache {
        Map<Integer,Node> map ;//哈希表
        int maxCap;//记录最大缓存容量
        DoubleList list;//双向链表
        public LRUCache(int capacity) {
            map=new HashMap();
            this.maxCap=capacity;
            list=new DoubleList();
        }
        
        public int get(int key) {
            if(!map.containsKey(key)){
               return -1; 
            }
            
            put(key,map.get(key).val);//删除原来位置,并把数据提到开头
            return  map.get(key).val;
    
        }
        
        public void put(int key, int value) {
            Node node=new Node(key,value);
            if(map.containsKey(key)){
                list.remove(map.get(key));
                list.addFirst(node);
                //更新数据
                map.put(key,node);
            }else{
                //不包含 添加进去 看是容量满了
                if(list.size==maxCap){
                    Node node2=list.removeLast();
                    map.remove(node2.key);
                }
                map.put(key,node);
                list.addFirst(node);
            }
        }
    }
    
    class DoubleList{
        //跟LRU没关系现在,你就只写双向链表的就行
        //属性: 头结点 尾结点 长度
        Node head,tail;
        int size=0;
    
        public void addFirst(Node x){
            if(head==null){
                head=tail=x;
            }else{
                 Node n = head;
                n.prev = x;
                x.next = n;
                head = x;
            }
            size++;
        }
         public void remove(Node x){
             if(head==x&&tail==x){
                 head=null;
                 tail=null;
             }else if(head==x){
                 x.next.prev=null;
                 head=x.next;
             }else if(tail==x){
                 x.prev.next=null;
                 tail=x.prev;
             }else{
                 x.prev.next=x.next;
                 x.next.prev=x.prev;
             }
             size--;
        }
        public Node removeLast(){
            Node node=tail;
            remove(tail);
            return node;
        }
        public int size(){
       
            return size;
        }
    }
    
    class Node{
        //Node属性有 key val  前驱节点  后继节点
        int key,val;
        Node prev,next;
        public Node(int key,int val){
            this.key=key;
            this.val=val;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/b233f7f3d98e4bf2b472b8d7aacafc27.png