网站维护需要什么技能,网站 建设的售后服务,教育机构在线咨询,wordpress vps阅读文本大概需要3分钟。0x01#xff1a;FIFO算法FIFO(First in First out)#xff0c;先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想#xff0c;比如作业调度(先来先服务)#xff0c;为什么这个原则在很多地方都会用到呢#xff1f;因为这个原则… 阅读文本大概需要3分钟。0x01FIFO算法 FIFO(First in First out)先进先出。其实在操作系统的设计理念中很多地方都利用到了先进先出的思想比如作业调度(先来先服务)为什么这个原则在很多地方都会用到呢因为这个原则简单、且符合人们的惯性思维具备公平性并且实现起来简单直接使用数据结构中的队列即可实现。 在FIFO Cache设计中核心原则就是如果一个数据最先进入缓存中则应该最早淘汰掉。也就是说当缓存满的时候应当把最先进入缓存的数据给淘汰掉。在FIFO Cache中应该支持以下操作; get(key)如果Cache中存在该key则返回对应的value值否则返回-1 set(key,value)如果Cache中存在该key则重置value值如果不存在该key则将该key插入到到Cache中若Cache已满则淘汰最早进入Cache的数据。 举个例子假如Cache大小为3访问数据序列为set(1,1),set(2,2),set(3,3),set(4,4),get(2),set(5,5) 则Cache中的数据变化为 (1,1) set(1,1) (1,1) (2,2) set(2,2) (1,1) (2,2) (3,3) set(3,3) (2,2) (3,3) (4,4) set(4,4) (2,2) (3,3) (4,4) get(2) (3,3) (4,4) (5,5) set(5,5) 那么利用什么数据结构来实现呢 下面提供一种实现思路 利用一个双向链表保存数据当来了新的数据之后便添加到链表末尾如果Cache存满数据则把链表头部数据删除然后把新的数据添加到链表末尾。在访问数据的时候如果在Cache中存在该数据的话则返回对应的value值否则返回-1。如果想提高访问效率可以利用hashmap来保存每个key在链表中对应的位置。0x02LFU算法 LFU(Least Frequently Used)最近最少使用算法。它是基于“如果一个数据在最近一段时间内使用次数很少那么在将来一段时间内被使用的可能性也很小”的思路。 注意LFU和LRU算法的不同之处LRU的淘汰规则是基于访问时间而LFU是基于访问次数的。举个简单的例子 假设缓存大小为3数据访问序列为set(2,2),set(1,1),get(2),get(1),get(2),set(3,3),set(4,4) 则在set(4,4)时对于LFU算法应该淘汰(3,3)而LRU应该淘汰(1,1)。 那么LFU Cache应该支持的操作为 get(key)如果Cache中存在该key则返回对应的value值否则返回-1 set(key,value)如果Cache中存在该key则重置value值如果不存在该key则将该key插入到到Cache中若Cache已满则淘汰最少访问的数据。 为了能够淘汰最少使用的数据因此LFU算法最简单的一种设计思路就是 利用一个数组存储 数据项用hashmap存储每个数据项在数组中对应的位置然后为每个数据项设计一个访问频次当数据项被命中时访问频次自增在淘汰的时候淘汰访问频次最少的数据。这样一来的话在插入数据和访问数据的时候都能达到O(1)的时间复杂度在淘汰数据的时候通过选择算法得到应该淘汰的数据项在数组中的索引并将该索引位置的内容替换为新来的数据内容即可这样的话淘汰数据的操作时间复杂度为O(n)。 另外还有一种实现思路就是利用 小顶堆hashmap小顶堆插入、删除操作都能达到O(logn)时间复杂度因此效率相比第一种实现方法更加高效。 如果哪位朋友有更高效的实现方式(比如O(1)时间复杂度)不妨探讨一下不胜感激。0x03LRU算法LRU算法的设计原则是如果一个数据在最近一段时间没有被访问到那么在将来它被访问的可能性也很小。也就是说当限定的空间已存满数据时应当把最久没有被访问到的数据淘汰。而用什么数据结构来实现LRU算法呢可能大多数人都会想到用一个数组来存储数据给每一个数据项标记一个访问时间戳每次插入新数据项的时候先把数组中存在的数据项的时间戳自增并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候将被访问的数据项的时间戳置为0。当数组空间已满时将时间戳最大的数据项淘汰。 这种实现思路很简单但是有什么缺陷呢需要不停地维护数据项的访问时间戳另外在插入数据、删除数据以及访问数据时时间复杂度都是O(n)。 那么有没有更好的实现办法呢 那就是利用链表和hashmap。当需要插入新的数据项的时候如果新数据项在链表中存在(一般称为命中)则把该节点移到链表头部如果不存在则新建一个节点放到链表头部若缓存满了则把链表最后一个节点删除即可。在访问数据的时候如果数据项在链表中存在则把该节点移到链表头部否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。 总结一下根据题目的要求LRU Cache具备的操作 1)set(key,value)如果key在hashmap中存在则先重置对应的value值然后获取对应的节点cur将cur节点从链表删除并移动到链表的头部若果key在hashmap不存在则新建一个节点并将节点放到链表的头部。当Cache存满的时候将链表最后一个节点删除即可。 2)get(key)如果key在hashmap中存在则把对应的节点放到链表头部并返回对应的value值如果不存在则返回-1。推荐阅读Spring Boot 最流行的 16 条实践SSM框架的面试常见问题【分布式】缓存穿透、缓存雪崩缓存击穿解决方案阿里P7给出的一份超详细 Spring Boot 知识清单关注我每天进步一点点你点的每个在看我都认真当成了喜欢
