高频考题-LRU缓存机制

2024-06-18 13:04
文章标签 缓存 机制 lru 高频 考题

本文主要是介绍高频考题-LRU缓存机制,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

146. LRU 缓存

LRU 缓存机制可以通过哈希表辅以双向链表实现,维护所有在缓存中的键值对。

双向链表按照读取的顺序存储键值对,靠近头部的键值对是最近使用的,尾部的键值对是最久未使用的。

哈希表即为普通的哈希映射(HashMap),通过缓存数据的键映射到其在双向链表中的位置。

这样以来,我们首先使用哈希表进行定位,找出缓存项在双向链表中的位置,随后将其移动到双向链表的头部,即可在 O(1)的时间内完成 get 或者 put 操作。具体的方法如下:

对于 get 操作,首先判断 key 是否存在:

  • 如果 key 不存在,则返回 −1;
  • 如果 key 存在,则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置,并将其移动到双向链表的头部,最后返回该节点的值。

对于 put 操作,首先判断 key 是否存在:

  • 如果 key 不存在,使用 key 和 value 创建一个新的节点,在双向链表的头部添加该节点,并将 key 和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量,如果超出容量,则删除双向链表的尾部节点,并删除哈希表中对应的项;
  • 如果 key 存在,则与 get 操作类似,先通过哈希表定位,再将对应的节点的值更新为 value,并将该节点移到双向链表的头部。
class LRUCache {private static class Node{int key, value;Node pre, next;Node(int k, int v){key = k;value = v;}}private final int capacity;private final Map<Integer, Node> keyToNode= new HashMap<>();private final Node dummy = new Node(0,0);public LRUCache(int capacity) {this.capacity = capacity;dummy.pre = dummy;dummy.next = dummy;}public int get(int key) {Node node = getNode(key);return node != null ? node.value : -1;}public void put(int key, int value) {Node node = getNode(key);if(node != null){node.value = value;return;}node = new Node(key,value);keyToNode.put(key,node);pushFront(node);if(keyToNode.size() > capacity){Node backNode = dummy.pre;keyToNode.remove(backNode.key);remove(backNode);}}// 哈希表获取key对应的Nodeprivate Node getNode(int key){if(!keyToNode.containsKey(key)){return null;}Node node = keyToNode.get(key);remove(node);pushFront(node);return node;}// 移除最后一个Nodeprivate void remove(Node x){x.pre.next = x.next;x.next.pre = x.pre;}// 将Node放到链表头部(借助哑元结点)private void pushFront(Node x){x.pre = dummy;x.next = dummy.next;x.pre.next = x;x.next.pre=x;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/

PS:

1.需要几个哨兵节点?

一个就够了。一开始哨兵节点 dummy的 prev 和 next都指向 dummy。随着节点的插入,dummy 的 next指向链表的第一个节点,prev指向链表的最后一个节点。

2.为什么用双向链表而不是单向链表?

将某个节点移动到链表头部或者将链表尾部节点删去,都要用到删除链表中某个节点这个操作。删除操作需要找到该节点的前驱节点和后继节点。对于寻找后继节点,单向链表和双向链表都能通过 next 指针在O(1)时间内完成;对于寻找前驱节点,单向链表需要从头开始找,也就是要O(n)时间,双向链表可以通过前向指针直接找到,需要O(1)时间。综上,要想在O(1)时间内完成该操作,当然需要双向链表,实际上就是用双向链表空间换时间了。

3.为什么链表节点需要同时存储 key 和 value,而不是仅仅只存储 value?

在删除链表末尾节点时,也要删除哈希表中的记录,这需要知道末尾节点的 key\textit{key}key。

这篇关于高频考题-LRU缓存机制的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1072072

相关文章

JVM 的类初始化机制

前言 当你在 Java 程序中new对象时,有没有考虑过 JVM 是如何把静态的字节码(byte code)转化为运行时对象的呢,这个问题看似简单,但清楚的同学相信也不会太多,这篇文章首先介绍 JVM 类初始化的机制,然后给出几个易出错的实例来分析,帮助大家更好理解这个知识点。 JVM 将字节码转化为运行时对象分为三个阶段,分别是:loading 、Linking、initialization

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

Java ArrayList扩容机制 (源码解读)

结论:初始长度为10,若所需长度小于1.5倍原长度,则按照1.5倍扩容。若不够用则按照所需长度扩容。 一. 明确类内部重要变量含义         1:数组默认长度         2:这是一个共享的空数组实例,用于明确创建长度为0时的ArrayList ,比如通过 new ArrayList<>(0),ArrayList 内部的数组 elementData 会指向这个 EMPTY_EL

【编程底层思考】垃圾收集机制,GC算法,垃圾收集器类型概述

Java的垃圾收集(Garbage Collection,GC)机制是Java语言的一大特色,它负责自动管理内存的回收,释放不再使用的对象所占用的内存。以下是对Java垃圾收集机制的详细介绍: 一、垃圾收集机制概述: 对象存活判断:垃圾收集器定期检查堆内存中的对象,判断哪些对象是“垃圾”,即不再被任何引用链直接或间接引用的对象。内存回收:将判断为垃圾的对象占用的内存进行回收,以便重新使用。

【Tools】大模型中的自注意力机制

摇来摇去摇碎点点的金黄 伸手牵来一片梦的霞光 南方的小巷推开多情的门窗 年轻和我们歌唱 摇来摇去摇着温柔的阳光 轻轻托起一件梦的衣裳 古老的都市每天都改变模样                      🎵 方芳《摇太阳》 自注意力机制(Self-Attention)是一种在Transformer等大模型中经常使用的注意力机制。该机制通过对输入序列中的每个元素计算与其他元素之间的相似性,

如何通俗理解注意力机制?

1、注意力机制(Attention Mechanism)是机器学习和深度学习中一种模拟人类注意力的方法,用于提高模型在处理大量信息时的效率和效果。通俗地理解,它就像是在一堆信息中找到最重要的部分,把注意力集中在这些关键点上,从而更好地完成任务。以下是几个简单的比喻来帮助理解注意力机制: 2、寻找重点:想象一下,你在阅读一篇文章的时候,有些段落特别重要,你会特别注意这些段落,反复阅读,而对其他部分

【Tools】大模型中的注意力机制

摇来摇去摇碎点点的金黄 伸手牵来一片梦的霞光 南方的小巷推开多情的门窗 年轻和我们歌唱 摇来摇去摇着温柔的阳光 轻轻托起一件梦的衣裳 古老的都市每天都改变模样                      🎵 方芳《摇太阳》 在大模型中,注意力机制是一种重要的技术,它被广泛应用于自然语言处理领域,特别是在机器翻译和语言模型中。 注意力机制的基本思想是通过计算输入序列中各个位置的权重,以确

Redis中使用布隆过滤器解决缓存穿透问题

一、缓存穿透(失效)问题 缓存穿透是指查询一个一定不存在的数据,由于缓存中没有命中,会去数据库中查询,而数据库中也没有该数据,并且每次查询都不会命中缓存,从而每次请求都直接打到了数据库上,这会给数据库带来巨大压力。 二、布隆过滤器原理 布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,它利用多个不同的哈希函数将一个元素映射到一个位数组中的多个位置,并将这些位置的值置

FreeRTOS内部机制学习03(事件组内部机制)

文章目录 事件组使用的场景事件组的核心以及Set事件API做的事情事件组的特殊之处事件组为什么不关闭中断xEventGroupSetBitsFromISR内部是怎么做的? 事件组使用的场景 学校组织秋游,组长在等待: 张三:我到了 李四:我到了 王五:我到了 组长说:好,大家都到齐了,出发! 秋游回来第二天就要提交一篇心得报告,组长在焦急等待:张三、李四、王五谁先写好就交谁的

UVM:callback机制的意义和用法

1. 作用         Callback机制在UVM验证平台,最大用处就是为了提高验证平台的可重用性。在不创建复杂的OOP层次结构前提下,针对组件中的某些行为,在其之前后之后,内置一些函数,增加或者修改UVM组件的操作,增加新的功能,从而实现一个环境多个用例。此外还可以通过Callback机制构建异常的测试用例。 2. 使用步骤         (1)在UVM组件中内嵌callback函