首页 > 其他分享 >BM100 设计LRU缓存结构

BM100 设计LRU缓存结构

时间:2024-08-15 17:53:41浏览次数:12  
标签:Node set get value 缓存 LRU BM100 key

1.题目描述

设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。
3. set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生,则认为这个key的记录成了最常使用的,然后都会刷新缓存。
2.当缓存的大小超过capacity时,移除最不经常使用的记录。
3.返回的value都以字符串形式表达,如果是set,则会输出"null"来表示(不需要用户返回,系统会自动输出),方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value,下面说明的缓存里key用""号包裹

数据范围:

1≤capacity<=1051≤capacity<=105
0≤key,val≤2×109 0≤key,val≤2×109 
1≤n≤1051≤n≤105
 

示例1

输入:

["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2

返回值:

["null","null","1","null","-1","null","-1","3","4"]

说明:

我们将缓存看成一个队列,最后一个参数为2代表capacity,所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存,缓存是{"1"=1},set操作返回"null"
s.set(2,2); //将(2,2)插入缓存,缓存是{"2"=2,"1"=1},set操作返回"null"
output=s.get(1);// 因为get(1)操作,缓存更新,缓存是{"1"=1,"2"=2},get操作返回"1"
s.set(3,3); //将(3,3)插入缓存,缓存容量是2,故去掉某尾的key-value,缓存是{"3"=3,"1"=1},set操作返回"null" 
output=s.get(2);// 因为get(2)操作,不存在对应的key,故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存,缓存容量是2,故去掉某尾的key-value,缓存是{"4"=4,"3"=3},set操作返回"null" 
output=s.get(1);// 因为get(1)操作,不存在对应的key,故get操作返回"-1"
output=s.get(3);//因为get(3)操作,缓存更新,缓存是{"3"=3,"4"=4},get操作返回"3"
output=s.get(4);//因为get(4)操作,缓存更新,缓存是{"4"=4,"3"=3},get操作返回"4"

2.解题思路

本题最关键的是我们需要一个数据结构,能让本次get/set的元素调整到最新访问的位置,并且以O(1)的时间复杂度找到最近最少使用的结点。

可以通过hashMap+双向链表的数据结构实现这个功能,例如当前get(key)已经存在,我们就现在双向链表和map中都删除掉这个 结点,然后再把这个结点加入到双向链表的表尾,表示最新访问过;如果put(key,val)中的key已经存在,也是需要先删除再重新加入,保证此次访问过后,这个结点就在最新访问的位置,如果Map中元素个数已经等于capacity,那就先删除最久未使用的那个结点,再加入新结点。

注:使用双向链表,只需要我们把要删除的结点当作形参传入,我们就可以以O(1)的复杂度找到它的前驱结点和后序结点,完成对该点的删除;同理,插入操作都是将结点插入到表尾,表示当前结点是最新被访问过的结点,也可以以O(1)的时间复杂度完成。

3.代码实现

import java.util.*;

class Node {
    public int key;
    public int val;
    public Node pre;
    public Node next;

    public Node(int key, int val) {
        this.key = key;
        this.val = val;
    }
}


public class Solution {
    private Map<Integer, Node> map = new HashMap();
    private Node left = null;
    private Node right = null;
    private int capacity;
    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        //left指向最久未使用的结点 right指向最新的结点
        left = new Node(-1, -1);
        right = new Node(-1, -1);
        left.next = right;
        right.pre = left;
    }

    public int get(int key) {
        // write code here
        if (map.containsKey(key)) {
            Node node = map.get(key);
            //删除链表中的该结点node
            remove(node);
            //在最新位置加入该结点
            insert(key, node.val);
            return node.val;
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)) {
            Node node = map.get(key);
            remove(node);
            insert(key, value);
        } else {
            if (map.size() == capacity) {
                //置换出最近最久未使用的结点
                Node del = left.next;
                remove(del);
                insert(key, value);
            } else {
                insert(key, value);
            }
        }
    }

    private void insert(int key, int val) {
        Node cur = new Node(key, val);
        Node pre = right.pre;
        cur.pre = pre;
        cur.next = right;
        pre.next = cur;
        right.pre = cur;
        map.put(key, cur);
    }


    private void remove(Node node) {
        Node pre = node.pre;
        Node next = node.next;
        pre.next = next;
        next.pre = pre;
        map.remove(node.key, node);
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

标签:Node,set,get,value,缓存,LRU,BM100,key
From: https://blog.csdn.net/cqjnovo/article/details/141228276

相关文章

  • 电脑怎么清理缓存数据,清理电脑缓存数据的方法
    清理电脑缓存数据是维护电脑性能和释放存储空间的重要步骤。以下是一些常见且有效的方法来清理电脑缓存数据:一、使用系统自带工具1.磁盘清理使用cleanmgr命令快速打开磁盘清理工具。在Windows系统中,可以使用磁盘清理工具来删除临时文件、系统文件、缩略图等缓存数据。打开“......
  • C盘里的缓存文件,C盘里的缓存文件怎么清理
    C盘中的缓存文件是系统或应用程序在运行过程中产生的临时数据,这些文件会随着时间的推移逐渐积累,占用大量的磁盘空间。为了释放C盘空间,提高系统运行效率,可以采取以下几种方法来清理C盘中的缓存文件:一、手动清理1.清理系统缓存文件:按下“Win+R”键,打开运行窗口,输入%temp%,点击......
  • 关于缓存的击穿、雪崩、穿透
    击穿:形象过程为当一个key过于火爆,很多用户同时查找这个key,造成高并发的同时这个缓存如果瞬间失效,导致大量业务进入数据库进行查询,造成性能差等一些问题。解决方法:1.设置缓存时间永不过期2.加锁排队,使其由并行成为串行。雪崩:在第一个的基础上,是多个key在同一时间缓存失效,或者......
  • List实现LRU
    publicclassLRUCache{intcap;LinkedHashMap<Integer,Integer>linkedHashMap=newLinkedHashMap<>();LRUCache(intcap){this.cap=cap;}publicintget(intkey){if(!linkedHashMap.containsKey(key......
  • 并发场景下,缓存失效处理场景
    并发场景下,缓存失效,需要从数据库或下游查询缓存中的数据。若并发流量都请求到下游,导致下游压力较大,可通过如下方式进行处理:importjava.util.concurrent.*;publicclassSingleFlight{privatefinalConcurrentMap<Object,CompletableFuture<?>>cache=newConcurrent......
  • pbootcms模板自动清理runtime缓存
    打开/apps/home/controller/ExtLabelController.php文件找到  //测试扩展单个标签  privatefunctiontest()  {    $this->content=str_replace('{pboot:userip}',get_user_ip(),$this->content);  }}在它下面加入//自动会话清理脚本publicfunc......
  • Spring Boot 缓存优化攻略
    1.确定待缓存的对象首先,我们需要明确哪些对象最适合缓存。一般而言,那些代价高昂且耗时的操作的结果需要优先考虑,例如数据库查询、网络服务调用或复杂计算的结果。然而,定义一些理想缓存候选对象的通用特征将更重要。这些特征有助于我们在应用程序中识别适合缓存的对象:频繁访......
  • 什么是缓存击穿、缓存穿透、缓存雪崩?
    1.缓存击穿(CacheBreakdown)定义:缓存击穿指的是缓存中某个热点数据在过期或被删除后,突然失效,导致大量请求同时到达数据库。由于热点数据的缓存失效,这些请求会同时直接访问数据库,导致数据库负载急剧增加。具体场景:假设一个电商平台的一个热销商品的库存信息被缓存了。......
  • windwos清理图标缓存
    有的时候桌面图标突然就没了,可以采用下面bat命令进行清理rem关闭Windows外壳程序explorertaskkill/f/imexplorer.exerem清理系统图标缓存数据库attrib-h-s-r"%userprofile%\AppData\Local\IconCache.db"del/f"%userprofile%\AppData\Local\IconCache.db"a......
  • jetcache缓存使用
    1、简介​ jetcache是阿里开源的一个缓存框架,支持像guava的cache、caffeine的Cache用法,也可以集成springboot,像spring的@Cache注解一样进行使用。​ jetcache的缓存类似于map,提供了get、put、putAll、computeIfAbsent等方法,另外还提供了单机锁、分布式锁机制,一般也不用这个......