力扣146|LRU缓存淘汰算法

LRU缓存淘汰算法

leet code146: https://leetcode.cn/problems/lru-cache

一、基本思想

1.1 基本思想

LRU全名Last Recently Used,即当缓存空间满时,优先淘汰最不常使用(访问)的缓存。

1.2 抽象接口

1、 init() 初始化大小为N的缓存空间

2、 put(key, val) 将id为key的缓存加入缓存空间,要求O(1)时间复杂度

3、get(key) 得到id为key的缓存,要求O(1)时间复杂度

明确行为:

要实现缓存访问时间的区别,所选的数据结构最好能保持元素有序。

在put存一个缓存时,有可能是插入,也有可能是更新。不论是插入还是更新,id为key的缓存页都被访问了一次,需要将它的优先级提高。插入时还需要考虑缓存满,需要选择一个缓存页淘汰。

在get一个缓存时,访问了一遍id为key的缓存,需要提高它的优先级。

二、代码实现

2.1 数据结构

插入删除要求O(1),自然是选择链表。

查找更新要求O(1),肯定是哈希表。

两者结合就形成了哈希链表,LinkedHashMap。

在这里插入图片描述

2.2 借助API实现

class LRUCache {
    int cap;
    // 插入队尾,就是最常使用的
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) {
        cap = capacity;
    }
    
    public int get(int key) {
        int val = -1;
        if(cache.containsKey(key)){
            // 得到值
            val = cache.get(key);
            // 提升这个值到队尾
            cache.remove(key);
            cache.put(key, val);
        }
        return val;
    }
    
    public void put(int key, int val) {
        if(cache.containsKey(key)){
            cache.put(key, val); //变更数据
            this.get(key);
            return;
        }else{
            // 插入需要先判断容量是否已满
            if(cache.size()>=this.cap){
                // 淘汰队首
                int oldKey = cache.keySet().iterator().next();
                cache.remove(oldKey);
            }
                cache.put(key, val);
            }
        }
    }
}

我们用链表存数据,最新的数据插入到队尾。

get要做的事情:得到key对应的值,将key优先级提高。

put要做的事情:判断key在不在链表中,相应的修改/插入操作行为。

​ 修改操作:修改值,提升优先级。

​ 插入操作:判断队伍空间是否满,已满需要淘汰队首。然后在插入。

2.3 自己实现哈希链表

(1)想明白

要做哪些事?

  • 自己实现双向链表
  • 利用HashMap哈希表
  • 整合这两个为哈希链表

哈希链表要实现哪些API?

  • get 根据key得到值
  • put 根据key进行修改或插入操作
  • remove 删除指定key

双向链表要实现的API:

  • 插入节点
  • 删除节点(给出Node)

(2)双向链表实现

class Node{
    public int key,val;
    public Node prev,next;
    Node(int key, int val){
        this.key = key;
        this.val = val;
        prev = null;
        next = null;
    }
}

class DoubleList{
    private Node dummyNode;
    public int size;
    DoubleList(){
        dummyNode = new Node(-1, -1);
        dummyNode.prev = dummyNode;
        dummyNode.next = dummyNode;
        size = 0;
    }
    public void insert(Node tmp){
       tmp.prev = dummyNode.prev;
       tmp.next = dummyNode;
       dummyNode.prev.next = tmp;
       dummyNode.prev = tmp;
       size+=1;
    }
    public void remove(Node tmp){
       if(size<=0) return;
       Node front  = tmp.prev;
       Node rear = tmp.next;
       front.next = rear;
       rear.prev = front;
       tmp.prev = null;
       tmp.next = null;
       size-=1;
    }
    public int removeFirst(){
        int ret = dummyNode.next.key;
        remove(dummyNode.next);
        return ret;
    }
}

技巧:

  • 伪头节点
  • 循环链表

(3) LRUCache实现文章来源地址https://www.uudwc.com/A/aYDR9/

class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;
    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        Node tmp = map.get(key);
        int val = -1;
        if(tmp==null) return val;
        val = tmp.val;
        cache.remove(tmp);
        cache.insert(tmp);
        return val;
    }
    
    public void put(int key, int val) {
        Node tmp = map.get(key);
        if(tmp==null){
            // 插入操作,判断队满
            if(cache.size == cap){
               int oldkey = cache.removeFirst();
               map.remove(oldkey);
            }
            Node new_tmp = new Node(key,val); 
            map.put(key, new_tmp);
            cache.insert(new_tmp);
        }else{
            // 更新操作
            cache.remove(tmp);
            tmp.val = val;
            cache.insert(tmp);
        }
    }
}

原文地址:https://blog.csdn.net/weixin_43538042/article/details/133412523

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请联系站长进行投诉反馈,一经查实,立即删除!

上一篇 2023年10月16日 08:55
78评价《乡村振兴战略下传统村落文化旅游旅游设计》许少辉博士新书
下一篇 2023年10月16日 09:55