LRU缓存机制

Myth丶恋晨 2023-08-17 16:50 92阅读 0赞

LRU 缓存机制现在都用 hashmap+ 双向链表实现了。

所以有的人直接用LinkedHashMap 重写一些方法实现。

但是也有链表和Map实现，原理就是 将每次使用的从原来位置删除，再移动到head节点，这样最近最久未使用的

就会被移动到链表后面。

**注意的点：**

**1.get()方法后，都必须remove()，再放在队首，remove()方法，setHead方法注意头节点，尾节点的位置。**

**2.remove()，判断各自pre,next，存在吗，不存在就操作head,end指针.3.setHead 方法，头插法，但是注意,新加入的头的pre必须置null,head.pre = node。指向问题，同时注意end == null,end = head问题；**

**3.set方法，存在key,覆盖，放队首，不存在，new一个节点后，再删除map中的end.key，删除链表，设置队首，再最后放入，map。**

1.hashmap

package com.hnist.lzn.sort;
    
    import java.util.HashMap;
    import java.util.LinkedHashMap;
    
    public class LRUCache {
    
       static class Node{
    
           int key;
           int value;
    
           Node pre;
           Node next;
    
           public Node(int key,int value){
    
               this.key = key;
               this.value = value;
           }
    
       }
       int capacity;
       HashMap<Integer,Node> map = new HashMap<>();
       Node head =null;
       Node end = null;
       public LRUCache(int c){
    
           this.capacity = c;
       }
    
       public int get(int key){
    
           // 0(1) 得到
           if(map.containsKey(key)){
               Node n = map.get(key);
               // 双向链表移除
               remove(n);
               // 设置到头节点那边
               setHead(n);
               return n.value;
           }
            return -1;
       }
    
       public void remove(Node n){
    
           if(n.pre!=null)
           {
                n.pre.next = n.next;
    
           }else{
    
               head = n.next;
           }
    
    
           if(n.next!=null)
           {
               n.next.pre = n.pre;
    
           }else{
    
              end = n.pre;
           }
    
       }
    
       public void setHead(Node n){
    
           // 链接起 n 到链表
           n.next = head;
    
           n.pre = null;
           // 这才算n 正式链接到链表中
           if(head!=null)
               head.pre = n;
    
           // head 指向链表第一个点
           head = n;
           // 判断尾节点是否为空
           if(end == null)
               end = head;
    
    
       }
    
       public void set(int key,int value){
    
           if(map.containsKey(key)){
                
                // 存在就替换
                Node old = map.get(key);
                old.value = value;
                remove(old);
                setHead(old);
           }else{
               // 不存在就插入
               // 新建节点
               Node created = new Node(key,value);
               
               // 大于就删除
               if(map.size()>=capacity){
    
                   map.remove(end.key);
                   remove(end);
                   setHead(created);
    
               }else{
                   setHead(created);
               }
    
               map.put(key,created);
           }
    
    
    
       }
    
     
    
    }

2.LinkedHashMap

class LRUCache extends LinkedHashMap<Integer, Integer>{
        private int capacity;
        
        public LRUCache(int capacity) {
            super(capacity, 0.75F, true);
            this.capacity = capacity;
        }
    
        public int get(int key) {
            return super.getOrDefault(key, -1);
        }
    
        public void put(int key, int value) {
            super.put(key, value);
        }
    
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return size() > capacity; 
        }
    }